Welcome to the Theory group's seminar series. You can subscribe to our cs-theory mailing list, our Google calendar, and our experimental RSS Feed.

If you are interested in giving a research presentation, please send an email to the organizer Peter Høyer.

The CS Theory Seminar Series runs on Fridays at 14:00-15:00 in ICT 616.

  1. Unsound inferences make proofs shorter Matthias Baaz [Vienna University of Technology, baaz(at)logic.at] Friday March 03, 2017 at 14:00-15:00 in ICT 616

    We give examples of analytic sequent calculi that extend Gentzen's sequent calculus LK by unsound quantifier rules in such a way that (i) derivations lead only to true sequents and (ii) cut free proofs may be non-elementary shorter than cut free LK proofs. This research is based on properties of Hilbert's epsilon calculus and part of efforts to complement Hilbert's stepwise concept of proof by useful global concepts.

    Joint work with Juan P. Aguilera

  2. Restriction lambda-calculus Jérôme Fortier [University of Ottawa, jerome.fortier(at)gmail.com] Friday January 27, 2017 at 14:00-15:00 in ICT 616

    One of the most general, and therefore nicest, families of models for the notion of partiality (as in partial functions: functions that may be undefined sometimes) in categorical terms is the notion of a restriction category. That is: we put a focus on the idea of restricting morphisms to the domain of other morphisms via a restriction operator. There is also a notion of a cartesian closed restriction category (CCRC), analogous to the regular notion of a CCC. This work is an attempt to prove the Curry-Howard property for CCRC's, by developing the corresponding syntax. Our solution is something like simply typed lambda-calculus, with a restriction operator. The resulting logic turns out to be substructural, and therefore very nice!

  3. Boundless tagging with bounded objects Zahra Aghazadeh [University of Calgary, zaghazad(at)ucalgary.ca] Friday November 18, 2016 at 14:00-15:00 in ICT 616

    A fundamental technique used in the design of shared memory algorithms is tagging, where shared variables get augmented with additional unique values, called tags. Their purpose is to distinguish different writes of the same value. A naive way to implement a tag is to increment a counter with each modification of the variable. However, this requires variables of unbounded size.

    In this talk, we present our new framework for tagging that allows processes to generate tags infinitely often, store or retrieve them from other variables, use them safely, and release them when they are not needed any more. Then, we present an efficient implementation of this framework. Our framework has a number of applications, even unexpected ones, such as distributed memory reclamation.

    The talk is based on a joint paper with Philipp Woelfel that appeared in DISC 2016.

  4. A complexity-based hierarchy for multiprocessor synchronization Rati Gelashvili [MIT, (at)] Friday April 01, 2016 at 14:00-15:00 in ICT 616

    Herlihy's elegant computability based Consensus Hierarchy has for many years been our best explanation of the relative power of various multiprocessor synchronization instructions. However, key to this hierarchy is treating these instructions as distinct objects, an approach that is far from the real-world where multiprocessor programs apply synchronization instructions to collections of arbitrary memory locations. We were surprised to realize that when considering instructions applied to memory locations, the computability based hierarchy collapses, leaving open the question of what better captures the power of various synchronization instructions.

    In this talk I will describe a first approach to answering this question. We show a new alternative hierarchy of synchronization instructions, classified by the space complexity of solving obstruction-free consensus. Our hierarchy provides a classification of combinations of known instructions that seems to fit with our intuition of how useful some are in practice while questioning the effectiveness of others. We show a tight characterization of the power of buffered read and write instructions that completely saturate our hierarchy. Interestingly, this result also applies to multi-location atomic assignments, such as those implied by hardware transactions.

    Joint work with Faith Ellen, Nir Shavit and Leqi Zhu.

  5. Quantum correlations: Dimension bounds and conic formulations [arXiv 1506] [arXiv 1507] Jamie Sikora [National University of Singapore, jamiesikora(at)gmail.com] Friday January 22, 2016 at 14:00-15:00 in ICT 616

    In this talk, I will discuss correlations that can be generated by performing local measurements on bipartite quantum systems.

    I'll present an algebraic characterization of the set of quantum correlations which allows us to identify an easy-to-compute lower bound on the smallest Hilbert space dimension needed to generate a quantum correlation. I will then discuss some examples showing the tightness of our lower bound. Also, the algebraic characterization can be used to express the set of quantum correlations as the projection of an affine section of the cone of completely positive semidefinite matrices. Using this, we identify a semidefinite programming outer approximation to the set of quantum correlations which is contained in the first level of the Navascués, Pironio and Acín hierarchy, and a linear conic programming problem formulating exactly the quantum value of a nonlocal game. Time permitting, I will discuss other consequences of these conic formulations and some interesting special cases.

    This talk is based on work with Antonios Varvitsiotis and Zhaohui Wei

  6. On the time and space complexity of ABA prevention and detection Zahra Aghazadeh [University of Calgary, zaghazad(at)ucalgary.ca] Friday October 30, 2015 at 14:00-15:00 in ICT 616

    Consider a shared memory system in which multiple processes communicate asynchronously by reading and writing shared variables. Since the beginning of using these shared memory systems, programmers and researchers have had to deal with the "ABA problem": Even though a process retrieves the same value twice in a row from a shared memory object, it is still possible that the value of the object has changed multiple times. In many shared memory algorithms and data structures people have dealt with the ABA problem in an ad-hoc, application specific way.

    In this talk we discuss how much time and space we need in general to detect and prevent ABAs in shared memory algorithms for systems with multiple processes while using bounded sized shared variables.

    The talk is based on a joint paper with Philipp Woelfel that appeared in PODC 2015.

  7. Tabulating strong pseudoprimes Andrew Shallue [Illinois Wesleyan University, ashallue(at)iwu.edu] Friday October 23, 2015 at 14:00-15:00 in ICT 616

    A positive integer n is a strong pseudoprime to the base a if it is composite, and yet passes the Miller-Rabin-Selfridge test for that base. Pseudoprimes are interesting because of their divisibility properties and because they shed light on the failure rate of the corresponding test. In this talk we discuss the asymptotic complexity of the problem of tabulating strong pseudoprimes.

  8. Computing Jacobi's theta function in quasi-optimal time Hugo Labrande [University of Calgary, hugo(at)hlabrande.fr] Friday October 16, 2015 at 14:00-15:00 in ICT 616

    Jacobi's theta function ϑ is a quasi-periodic complex-valued function that appears in numerous fields, from number theory to differential equations. We outline a new algorithm that computes ϑ(z,τ) in O(log P) multiplications of P-bit complex numbers; this is asymptotically faster than the naïve algorithm, which requires O(P^0.5) such multiplications. Our approach is similar to an existing algorithm that computes ϑ(0,τ) in O(log P) multiplications; we use a quadratically convergent sequence inspired by the arithmetico-geometric mean of Gauss, and Newton's method.

    The first part of the talk will recall the computation of classical functions using fast, quasi-optimal time algorithms related to the using links with the AGM, and should be of broad interest. The second part will outline the algorithm that computes ϑ(0,τ) in quasi-optimal time, using the AGM and Newton's method; we will then outline our algorithm to compute ϑ(z,τ) for any z, which uses a very similar approach along with a few of the properties of the ϑ function, and present the results of our implementation.

  9. Controlled quantum amplification Catalin Dohotaru [University of Calgary, dcatalin(at)ucalgary.ca] Friday October 09, 2015 at 14:00-15:00 in ICT 616

    We give a novel, general framework which amplifies to a constant the success probability of any quantum search algorithm. Given a quantum search algorithm A, we design a new circuit that controls the evolution of A. We then develop a toolbox to express the complexity of the new, controlled operator in terms of the complexity of A. Whenever A can determine in some number of iterations if a unique solution exists, our circuit finds that solution within the same asymptotic cost. As one application of our framework, we conclude that finding is as easy as decision for quantum random walks with a unique solution.

    We assume no prior knowledge of quantum computing.

    This is joint work with Peter Høyer.

  10. Test-and-set in optimal space Maryam Helmi [University of Calgary, mhelmikh(at)ucalgary.ca] Friday October 02, 2015 at 14:00-15:00 in ICT 616

    The test-and-set object is a fundamental synchronization primitive for shared memory systems. In this talk I will address the number of registers required to implement a one-shot test-and-set object in the standard asynchronous shared memory model with n processes.

    Styer and Petterson and later Giakkoupis and Woelfel proved a lower bound of log(n-1) for deadlock-free and obstruction-free implementations. In this talk I will present an asymptotically tight algorithm using O(log n) registers of size O(log n) bits. Combining this obstruction-free algorithm with techniques from previous research, I also show a randomized wait-free test-and-set algorithm from log(n) registers, with expected step-complexity log*(n) against the oblivious adversary. The core tool in this algorithm is the implementation of a deterministic obstruction-free sifter object, using only 6 registers. If k processes access a sifter, then when they have terminated, at least one and at most 2k/3 processes return 'win' and all others return 'lose'.

  11. Secure communication over unreliable channels Rei Safavi-Naini [University of Calgary, rei.safavi(at)gmail.com] Friday September 25, 2015 at 14:00-15:00 in ICT 616

    The most basic question in secure communication is ensuring that if a message is sent by Alice, it will be received correctly and securely by Bob. Answering this question scientifically, requires developing an abstract model for the communication system and defining the required properties. I will give an overview of important existing approaches, and outline some of our recent work on a new model and construction.

  12. Wait-freedom is harder than lock-freedom under strong linearizability Oksana Denysyuk [University of Calgary, oksana.denysyuk(at)gmail.com] Friday September 18, 2015 at 14:00-15:00 in ICT 616

    In randomized algorithms, replacing atomic shared objects with linearizable [TOPLAS'90] implementations may affect probability distributions over outcomes [STOC'11]. To avoid this problem in the adaptive adversary model, it is necessary and sufficient that implemented objects satisfy strong linearizability [STOC'11].

    In this talk we address the existence of strongly linearizable implementations from multi-writer registers. We prove the impossibility of wait-free strongly linearizable implementations for a number of standard objects, including snapshots, counters, and max-registers, all of which have wait-free linearizable implementations. To do so, we introduce a new notion of group valency that is useful to analyze (strongly linearizable) implementations from registers. Furthermore, we show that many objects, including snapshots, do have lock-free strongly linearizable implementations. These results separate lock-freedom from wait-freedom under strong linearizability.

    This is joint work with Philipp Woelfel.

  13. Functional encryption for cascade automata Dan Brownstein [Ben-Gurion University, brownstein.dan(at)gmail.com] Friday August 28, 2015 at 14:00-15:00 in ICT 616

    We introduce a functional encryption scheme based on the security of bilinear maps for the class of languages accepted by extended automata. In such an automaton, n DFAs, each with at most q states, are linked in a cascade such that the first DFA receives the input to the system and a feedback symbol from the last DFA, and in each transition the i-th DFA, i=1,...,n, both performs its own transition and outputs a symbol that acts as the input for DFA number i+1modulo n. The state of the whole system is an n-tuple consisting of the state of each component DFA. Our work extends the work of Waters (Crypto'12) by replacing a single DFA with a cascade. Although both models accept all regular languages, a cascade automata reduces the number of states and therefore the key size for certain regular languages by an exponential factor. In both systems, a message m is encrypted with a word w and can be decrypted only by a key that is associated with an automaton that accepts w. Our scheme has key size O(nq^2) and all its other efficiency measures including the ciphertext length, encryption and decryption times are linear in the length of w. As an example of the additional power that a cascade provides, we show a construction of a cascade that accepts a word in a regular language only if it is accompanied by a standard public key signature on that word.

    Our work improves on alternative approaches using functional encryption for general circuits or programs, by either being based on weaker assumptions, i.e. bilinear maps, or by being more efficient.

  14. Algebraic methods in the congested clique Keren Censor-Hillel [Technion, ckeren(at)cs.technion.ac.il] Friday March 27, 2015 at 14:00-15:00 in ICT 616

    In this talk, I will discuss algebraic methods for studying distance computation and subgraph detection tasks in the congested clique model of distributed computation. Specifically, we adapt parallel matrix multiplication implementations to the congested clique, obtaining an O(n^{1-2/omega}) round matrix multiplication algorithm, where omega < 2.373 is the exponent of matrix multiplication. This allows obtaining significantly faster algorithms for triangle and 4-cycle counting, APSP, computing the girth, and more.

    No previous knowledge in distributed computing will be assumed. Based on joint work with Petteri Kaski, Janne H. Korhonen, Christoph Lenzen, Ami Paz and Jukka Suomela.

  15. Vertex connectivity under vertex sampling George Giakkoupis [INRIA Rennes, george.giakkoupis(at)inria.fr] Friday March 06, 2015 at 14:00-15:00 in ICT 616

    A fundamental result by Karger (1994) states that for any k-edge connected graph with n nodes, independently sampling each edge with probability p = Ω(logn / k) results in a graph that has edge connectivity Ω(kp), with high probability. We prove the analogous result for vertex connectivity when independently sampling vertices. We show that for any k-vertex-connected graph with n nodes, if each node is independently sampled with probability p = Ω(sqrt{logn / k}) then the subgraph induced by the sampled nodes has vertex connectivity Ω(kp^2) with high probability. This bound is existentially optimal.

    This is a joint work with Keren Censor-Hillel, Mohsen Ghaffari, Bernhard Haeupler and Fabian Kuhn, and appeared at SODA'15.

  16. Yesquel: scalable SQL storage for web applications Marcos Aguilera [VMware, mkaguilera(at)gmail.com] Friday February 13, 2015 at 14:00-15:00 in ICT 618B

    Web applications (web mail, web stores, social networks) keep massive amounts of data that must be readily available to users. The storage system underlying these applications has evolved dramatically over the past 25 years, from file systems, to SQL database systems, to a large variety of NOSQL systems. In this talk, we contemplate this fascinating history and present a new storage system called Yesquel. Yesquel combines several advantages of prior systems. It supports the SQL query language to facilitate the design of Web applications, while offering performance and scalability of NOSQL systems.

  17. Distance bounding using time-stamps Xifan Zheng [University of Calgary, xzheng(at)ucalgary.ca] Friday January 30, 2015 at 14:00-15:00 in ICT 616

    Distance bounding protocol allows a prover to prove to a trusted verifier that it is within a distance bound B from the verifier. Implementing secure distance bounding protocol is challenging because of the need for fast processing at the prover. This also limits possible applications for distance bounding protocols.

    We propose a new approach to distance bounding using one-way transmission time (instead of round-trip time) to estimate the distance and so effectively remove the restriction on the prover's computation. To prove security we formalize the notion of time in a distributed environment using timestamps and use that to formalize security of distance bounding protocols and finally prove security of our protocol.

  18. Types and functions since Principia and the computerization of language and mathematics Fairouz Kamareddine [Heriot-Watt University, fairouz(at)macs.hw.ac.uk] Friday January 23, 2015 at 14:00-15:00 in ICT 616

    Historically functions have been treated as a kind of meta-object. This all changed with the work of Frege, Russell and Church. Furthermore, the challenges of the paradoxes led to the formalisation of type theory by Russell. Since, functions and types have gone through a long process of evolution through various degrees of abstraction, construction and evaluation making both functions and types first class citizens as far away from meta-level as possible. In this talk, I argue that desirable properties of the historic lower order approach (decidability, easiness of calculations) can be maintained without losing the flexibility of the higher-order aspects. I argue that the low level approach is still worthwhile for many exact disciplines.

  19. Exploiting interference to reduce communication time in wireless networks Mohsen Mollanoori [University of Calgary, mmollano(at)ucalgary.ca] Friday January 16, 2015 at 14:00-15:00 in ICT 616

    In wireless networks, if multiple packets are transmitted at the same time on the same channel, then the received signal is a combination of the transmitted signals. Traditionally, this is considered as a collision that requires retransmission of the packets. Modern decoding techniques, however, are able to extract useful information from multiple overlapping packets. Successive interference cancellation (SIC) and Physical-layer network coding (PNC) are two such techniques. In this talk, we examine the impact of these two techniques on the number of time slots required to achieve two different objectives, called Uploading and Synchronization, in a wireless network consisting of several terminals and a relay node. We analyze the time complexity of a few different problems arising from this setting. Specifically, PNC is only effective for Synchronization and there is a polynomial time algorithm to find the minimum number of time slots. In contrast, SIC reduces the number of time slots for both objectives, but finding the minimum is NP-hard. Approximation or randomized algorithms are suggested for some NP-hard cases. Some interesting problems remain open when PNC and SIC are combined.

  20. Valiant's universal circuit construction Saeed Sadeghian [University of Calgary, sadeghis(at)ucalgary.ca] Friday January 09, 2015 at 14:00-15:00 in ICT 616

    A Universal Circuit UCn is a circuit that can simulate any circuit C of size n, given the description of C as input. In this talk, we look back at the universal circuit construction of Valiant, from STOC 1976. Although the construction yields universal circuits with the best known asymptotic complexity, and has been employed in several recent works in the cryptography community, many details are unspecified, and somewhat surprisingly, no implementations of the construction exist. We give a complete description of Valiant's construction based on our new understanding, and the first implementation. We also observe that simple adaption of the same ideas to arithmetic circuits yield the first size optimized Universal Arithmetic circuit. Our implementation will be incorporated in implementation of new "private function evaluation" protocol.

  21. Genus 2 hyperelliptic curve cryptography [MSc Thesis] Sebastian Lindner [University of Calgary, salindne(at)ucalgary.ca] Friday November 28, 2014 at 14:00-15:00 in ICT 616

    Curve based cryptography has become a significant part of the world public key cryptography scene in the last 10 years. The smaller bit security that is needed when compared to more traditional protocols is ideal for communication where bandwidth is costly or limited. Elliptic curve cryptography is the standard used today, but a significant amount of work is being done in the generalized version of Hyperelliptic curve cryptography to produce more efficient protocols with the same security.

    The most important and costly operation of (hyper) elliptic curve public key exchange is scalar multiplication of the additive group elements. We present recent advancements on speeding up the scalar multiplication algorithms and also on speeding up the binary operations (doubling, addition, tripling) that the scalar multiplication algorithms use. Our thesis work is reflected in the last part. Fast binary operations directly affect the speed of scalar multiplication and in turn the efficiency of Hyperelliptic curve protocols.

  22. Tabulating class groups of quadratic fields Michael Jacobson, Jr. [University of Calgary, jacobs(at)ucalgary.ca] Friday November 21, 2014 at 14:00-15:00 in ICT 616

    Class groups of quadratic fields have been studied since the time of Gauss, and in modern times have been used in applications such as integer factorization and public-key cryptography. Tables of class groups are used to provide valuable numerical evidence in support of a number of unproven heuristics and conjectures, including those due to Cohen and Lenstra. In this talk, we discuss recent efforts to extend existing, unconditionally correct tables of both imaginary and real quadratic fields.

  23. Space bounds for renaming Maryam Helmi [University of Calgary, mhelmikh(at)ucalgary.ca] Friday November 14, 2014 at 14:00-15:00 in ICT 616

    In this talk, I will discuss the space complexity of implementing long-lived and one-shot renaming from registers, in an asynchronous shared memory system. In f(k)-renaming each of k participating processes gets a distinct name from the set {1,...,f(k)}. Our first result states that any obstruction-free long-lived f(k)-renaming algorithm uses at least m registers, where m be the largest integer such that f(m) <=i<= n-1, and n is the maximum number of processes in the system. Our next result is a lower bound of n/(c+1) registers for any obstruction-free one-shot (k+c)-renaming algorithm, for a constant c>0. Finally, we present a wait-free one-shot ((3k)^2 / 2)-renaming algorithm that uses just n^(1/2) registers.

    This is a joint work with Lisa Higham and Philipp Woelfel.

  24. Reversible computation and inverse categories [PhD thesis] Brett Giles [University of Calgary, brett.giles(at)ucalgary.ca] Friday November 07, 2014 at 14:00-15:00 in ICT 616

    In 1961, Rolf Landauer showed that irreversible computing had an unavoidable energy expenditure, caused by erasing information. This raised interest in reversible computing, as it might be able to avoid this energy cost. In 1973, Charles Bennett showed that a standard Turing machine could be simulated with a reversible Turing machine. Since that time researchers have created reversible languages and investigated reversible processes — such as unitary transforms in quantum computing.

    However, there has not been a unifying semantics for reversible computing. In this talk, I will present such a semantics, which uses inverse categories. These are categories whose maps are partial isomorphisms. The talk will not assume a background in category theory, rather, I will use partial injective functions as an example of inverse categories. This research formed part of my PhD thesis.

  25. Making objects writable [PODC 2014] Zahra Aghazadeh [University of Calgary, zaghazad(at)ucalgary.ca] Friday October 24, 2014 at 14:00-15:00 in ICT 616

    In shared memory systems, such as multi-core computers, processes communicate through shared objects that support atomic operations such as Compare & Swap, Test & Set or Fetch & Add. Often these primitives are only provided in software, e.g. in Java. Many of those primitives do not provide a write operation that unconditionally changes the state of the object to a new state given as argument.

    In this presentation, I will present a technique for augmenting almost any shared object with a linearizable and wait-free write operation, using bounded space and asymptotically optimal worst-case step complexity.

    The talk is based on a joint paper with Wojciech Golab and Philipp Woelfel that appeared in PODC 2014.

  26. Randomized mutual exclusion in O(1) RMRs [FOCS 2014] Philipp Woelfel [University of Calgary, woelfel(at)ucalgary.ca] Friday October 03, 2014 at 14:00-15:00 in ICT 616

    Mutual exclusion is one of the best studied shared memory problems. Algorithms solving this problem are fundamental for systems that rely on synchronization. Performance is usually measured in terms of remote memory references (RMRs).

    It is known that no deterministic mutual exclusion algorithm with sub-logarithmic RMR complexity exists. Despite several attempts to find more efficient randomized mutual exclusion algorithms, the question whether randomization can yield significant performance benefits without sacrificing other properties (in particular deterministic deadlock-freedom) remained open. In this talk I will present a randomized mutual exclusion algorithm that achieves expected constant amortized RMR complexity in the Distributed Shared Memory (DSM) model.

    The talk is based on a joint paper with George Giakkoupis that will appear in FOCS 2014.

  27. Team based learning in theoretical computer science courses Nathaly Verwaal [University of Calgary, verwaal(at)cpsc.ucalgary.ca] Friday April 25, 2014 at 14:00-15:00 in ICT 616

    Design and Analysis of Algorithms are generally acknowledged to be vital to the formation of fully rounded Computer Scientists, because abstract design approaches are applicable to all areas of Computer Science. Yet, designing and analyzing algorithms remains one of the main areas in which Computer Science students struggle. Students perceive the subject as being both extremely difficult (low student efficacy) and of little value, and students often repeat the course multiple times before they are able to earn a passing grade.

    A flipped classroom with a team based learning approach was introduced into our Design and Analysis of Algorithms course in 2013 with the aim of increasing both the value that students see in the material, their perceived efficacy and to improve the depth of their learning. This session will report on the tools used to deliver the course the methods used to evaluate the effectiveness of the delivery, the results that were observed and plans for further course development.

  28. A general technique for non-blocking trees Faith Ellen [University of Toronto, faith(at)cs.toronto.edu] Friday February 14, 2014 at 14:00-15:00 in ICT-516

    A library of concurrent data structures can make the task of developing concurrent software much easier. Although sequential data structures can be transformed into concurrent data structures in straightforward ways using locks or transactional memory, the results are generally inefficient. I will describe a general method for obtaining efficient non-blocking implementations of a large class of trees, including a chromatic tree, which is a relaxed version of a red-black tree, using only standard machine instructions.

    This is joint work with Trevor Brown and Eric Ruppert.

  29. Randomized rumor spreading in dynamic graphs George Giakkoupis [INRIA Rennes, ggiakk(at)gmail.com] Friday November 29, 2013 at 14:00-15:00 in ICT 616

    Randomized rumor spreading is a standard model of information dissemination, in which nodes exchange information with random network neighbors at each step. It has been used extensively as a protocol for communication networks, and also as a basic model for dissemination processes in social networks. Further, the number of steps needed to spread a piece of information has been analyzed for a wide range of network topologies, from fully connected graphs to random graph models for social networks. Almost all studies on randomized rumor spreading so far make the assumption that the network topology does not change during the dissemination. However, many of the prevalent topologies today, such as peer-to-peer and wireless networks, or online social networks, are inherently dynamic. In this talk, we will look at a general dynamic setting, which assumes that the connections between nodes may change after each step. We will discuss the impact of such changes on the time to spread a piece of information, and provide some general bounds in terms of expansion properties of the dynamic network.

    This is joint work with Thomas Sauerwald and Alexandre Stauffer.

  30. A space optimized leader election algorithm Maryam Helmi [University of Calgary, mhelmikh(at)ucalgary.ca] Friday November 15, 2013 at 14:00-15:00 in ICT 616

    Our model of computation is the standard asynchronous shared memory system with n processes. I present a deterministic obstruction-free leader election algorithm that uses sqrt(n) bounded registers in this model. Then I provide a technique to transform this algorithm into a randomized wait-free algorithm for the oblivious adversary.

  31. Geometric information flow Zongpeng Li [University of Calgary, zongpeng(at)ucalgary.ca] Friday October 18, 2013 at 14:00-15:00 in ICT 616

    Geometric information flow is a relatively new research direction that both (a) models the blueprinting of a communication network and (b) serves as a new tool for studying hard problems in network information flow. A key open problem here is to determine the computational complexity of the geometric information flow problem. We have thoughts on a hopefully polynomial-time algorithm, but are currently stuck. Your comments and feedback are welcome!

  32. The three squares problem, quaternion arithmetic, and number factoring Anton Mosunov [University of Calgary, asmosuno(at)ucalgary.ca] Friday September 27, 2013 at 14:00-15:00 in ICT 616

    Given an integer N, a three squares problem asks to find any three integers x, y, z such that N=x^2+y^2+z^2. It was Gauss who first noted that the total number R of these 〈x, y, z〉 representations is connected to the problem of finding a factor of N. With a further development of quaternion theory, now we know that not only R, but also certain relationships between those representations can give us an information about the factor of N. In my talk, I am going to present a number of algorithms used to manipulate those 〈x, y, z〉 representations as integral quaternions of the form xi+yj+zk. Each quaternion of that form generate a so-called "quadratic order," and these algorithms will be used to demonstrate the connection between various quadratic orders. Finally, as a consequence of these explorations, I will briefly describe the proof of a curious theorem, which states that for any 〈x, y, z〉 representation there exists another one, which allow us to yield the factor of N.

  33. Dynamic graph connectivity in polylogarithmic worst case time [SODA 2013] Valerie King [University of Victoria, val(at)uvic.ca] Friday April 12, 2013 at 15:00-16:00 in ICT 516

    The dynamic graph connectivity problem is the following: given a graph on a fixed set of n nodes which is undergoing a sequence of edge insertions and deletions, answer queries of the form Q(a,b): "Is there a path between nodes a and b?" While data structures for this problem with polylogarithmic amortized time per operation have been known since the mid-1990's, these data structures have Θ(n) worst case time. In fact, no previously known solution has worst case time per operation which is o(√n). In this talk I'll explain a solution with worst case times O(log^4(n)) per edge insertion, O(log^5(n)) per edge deletion, and O(log n/log log n) per query. The answer to each query is correct if the answer is "yes" and is correct with high probability if the answer is "no." The data structure is based on a simple novel idea which can be used to quickly identify an edge in a cutset.

    This work is joint with Bruce Kapron and Ben Mountjoy.

  34. Secure routing in wireless networks Majid Ghaderi [University of Calgary, mghaderi(at)ucalgary.ca] Friday April 05, 2013 at 15:00-16:00 in ICT 616

    There is a rich recent literature on how to assist secure communication between a single transmitter and receiver at the physical layer of wireless networks through techniques such as cooperative jamming. In this talk, we will discuss how these single hop physical layer security techniques can be extended to multi-hop wireless networks. Specifically, we will introduce the secure minimum energy routing problem, in which the objective is to compute a minimum energy path between two network nodes subject to constraints on the end-to-end communication secrecy and goodput over the path. This problem is formulated as a constrained optimization of transmission power and link selection, which is proved to be NP-hard. Nevertheless, we show that efficient algorithms exist to compute both exact and approximate solutions for the problem. In particular, we will present an exact solution of pseudo-polynomial complexity, as well as an epsilon-optimal approximation of polynomial complexity.

    This is a joint work with Dennis Goeckel, Ariel Orda and Mostafa Dehghan.

  35. Long-lived test-and-set and concurrent memory reclamation Zahra Aghazadeh [University of Calgary, zaghazad(at)ucalgary.ca] Friday March 01, 2013 at 15:00-16:00 in ICT 616

    Test-And-Set (TAS) objects are standard synchronization primitives for concurrent shared memory algorithms that can, for example, be used to protect a critical section in a mutual exclusion algorithm. A TAS object stores a bit, whose value is initially 0, and allows two operations: Test-And-Set(), which anatomically sets the bit and returns its previous value, and reset(), which resets the bit to 0. Recently, there has been significant progress on implementing efficient randomized one-shot TAS objects (which cannot be reset) from registers, but for many applications we need long-lived TAS objects (which can be reset repeatedly). It is easy to implement long-lived TAS objects from one-shot ones, but the trivial implementation requires an unbounded amount of space.

    I will show how to implement long-lived TAS objects from a bounded number of one-shot ones. This algorithm is part of a more general "recycling" technique that can be used to efficiently (with respect to space and time) reset shared objects.

  36. Expressing a multi-qubit operator in terms of simpler operators [arXiv] Brett Giles [University of Calgary, brett.giles(at)ucalgary.ca] Friday January 11, 2013 at 15:00-16:00 in ICT 616

    An important question in the field of compilers for quantum programming languages is how best to approximate an arbitrary quantum transform in terms of a given set of quantum operators. This is referred to as "synthesis". One can further break this down into the questions of "exact synthesis", where the original operator is expressed exactly, and "approximate synthesis" where the operator is expressed up to some error ε. Much of the work on synthesis targets the set of operators "Clifford+T". A recent result by Kliuchinkov, Maslov, and Mosca answered the question of exact synthesis for single qubit operators - any unitary operation whose matrix is expressible in Z[1/√2,i] is a product of Clifford+T operators. In that same paper, they conjectured this would also hold for n-qubit operators. In this talk, I will show their conjecture is correct. The proof uses elements of abstract and linear algebra (at a level normally found in 1st or 2nd year courses) and induction on the size of the matrix. Based upon our result, Kliuchinkov, Maslov, and Mosca recently published a paper on approximate synthesis where the approximation of a single qubit gate can be done using O(log 1/ε) gates, a significant improvement of the state of the art in approximate synthesis.

  37. Tight lower bounds for greedy routing in higher-dimensional small-world grids Philipp Woelfel [University of Calgary, woelfel(at)ucalgary.ca] Friday November 30, 2012 at 14:00-15:00 in ICT 616

    In 2000, Kleinberg proposed his celebrated Small World Graph model: Take an N &#215; N grid (the base graph); then add for each node u a directed link to some other randomly chosen node, v, called long-range contact of u. Kleinberg studied the time it takes to route between two nodes in the resulting augmented grid, using a simple decentralized grouting algorithm (greedy routing). In particular, he showed for some carefully chosen probability distribution that the expected greedy routing time between any two nodes is O(log^2 N). This result had a significant impact on algorithmic network applications, e.g., several peer-to-peer networks are based on similar Small World Graph models.

    In this talk I will discuss a new lower bound which states that there is no "natural" probability distribution for long-range contacts which can yield an expected greedy routing time of o(log^2 N) between any two nodes. (The lower bound holds also for higher dimensional grids.) The proof is based on a new technique which introduces a so-called probability budget game, in which a player has to walk across a game board and in each round has to bet a portion of a given budget. The progress the player makes depends on the amount she bet, but also results in a loss of budget.

    This is joint work with Martin Dietzfelbinger.

  38. Leakage-resilient detection of algebraic manipulation [Background paper] Hadi Ahmadi [University of Calgary, hahmadi(at)ucalgary.ca] Friday November 23, 2012 at 14:00-15:00 in ICT 616

    Cramer at al. studied algebraic manipulation detection (AMD) codes in an abstract storage model that does leak any information to the adversary. We develop this study further and consider scenarios where the adversary receives arbitrary (but bounded) information about the codeword through leakage. We refer to codes that protect against algebraic manipulation in this scenario as leakage-resilient (LR)-AMD codes. The adversary has unbounded computational power and yet there is no shared key (or correlated randomness) between the parties.

    We prove lower bounds on the minimum additional storage (redundancy) required by LR-AMD codes, and show optimal construction of such codes. We also define and introduce block-leakage-resilient (BLR)-AMD code constructions that work for certain leakage scenarios while requiring negligible redundancy. We show two applications of LR-AMD and BLR-AMD codes in cryptography: First, adding robustness to linear nonperfect secret sharing schemes and second, detection of algebraic manipulation over wiretap channels. Finally, we show how our BLR-AMD code construction can be composed with other primitives to provide unlimited bitwise manipulation detection, in addition to privacy, in message transmission or key agreement over binary symmetric and binary erasure channels. We discuss our results and show directions for future research.

  39. Encoding circuits for quantum codes Markus Grassl [Centre for Quantum Technologies, Singapore, Markus.Grassl(at)nus.edu.sg] Friday October 12, 2012 at 14:00-15:00 in ICT 616

    Quantum error-correcting codes (QECC) are an important component of any future quantum computing device. After a brief introduction to QECCs and in particular stabilizer quantum codes, we present various methods efficiently compute encoding circuits for QECCs.

    The talk does not assume any background in quantum information.

  40. Tau conjecture and angular distribution of roots of a polynomial Pavel Hrubeš [University of Calgary, pahrubes(at)gmail.com] Friday September 21, 2012 at 14:00-15:00 in ICT 616

    The so called tau conjecture states that a polynomial which is easy to compute has a small number of rational roots. If true, it gives long sought strong circuit lower bounds. I will discuss modifications of the conjecture, related to the number of real -- rather than rational -- roots, and the angular distribution of complex roots. In this setting, the conjecture can be seen as an extension of classical results in real or complex analysis, such as Descartes' rule of signs.

  41. The multiple unicast network coding conjecture [NetCod2012] [Paper] Zongpeng Li [University of Calgary, zongpeng(at)ucalgary.ca] Friday September 14, 2012 at 14:00-15:00 in ICT 616

    Network coding invites the "mixing" of data within a network, via means of encoding/decoding. Originally proposed in the field of information theory, network coding has witnessed a large series of applications in computer networks. The multiple unicast conjecture states that for multiple independent one-to-one unicast transmissions in an undirected network, network coding is equivalent to routing, in that a throughput vector r is feasible with network coding if and only if it is feasible with routing. Simple and intuitive as it appears, the conjecture has remained open since its proposal in 2004, and is now a well-known unsolved problem in the field of network coding. This talk aims to (a) quickly review the idea of network coding, (b) introduce the multiple unicast conjecture, and (c) discuss our ongoing effort in trying to prove the conjecture, based on a new geometric framework.

  42. Tight thresholds for cuckoo hashing via XORSAT Martin Dietzfelbinger [Technische Universitaet Ilmenau, martin.dietzfelbinger(at)tu-ilmenau.de] Thursday August 23, 2012 at 14:00-15:00 in ICT 616

    We report on settling the question of tight thresholds for offline cuckoo hashing. The problem can be stated as follows: we have n keys to be hashed into m buckets each capable of holding a single key. Each key has k>=3 (distinct) associated buckets chosen uniformly at random and independently of the choices of other keys. A hash table can be constructed successfully if each key can be placed into one of its buckets. We seek thresholds t(k) such that, as n goes to infinity, if n/m<=T for some T < t(k), then a hash table can be constructed successfully with high probability, and if n/m>=T for some T>t(k) a hash table cannot be constructed successfully with high probability. Here we consider the offline version of the problem, where all keys and hash values are given, so the problem is equivalent to previous models of multiple-choice hashing. We find the thresholds for all values of k>2 by showing that they are in fact the same as the previously known thresholds for the random k-XORSAT problem. We then extend these results to the setting where keys can have differing number of choices. Independently, with different methods, the threshold problem was solved by Fountoulakis/Panagiotou and Frieze/Melsted. In the meantime, generalized versions have been settled as well.

    (Joint work with Andreas Goerdt, Michael Mitzenmacher, Andrea Montanari, Rasmus Pagh, Michael Rink)

  43. Geometric tests with interval arithmetic and exact computation Jon Rokne [University of Calgary, rokne(at)ucalgary.ca] Friday April 13, 2012 at 15:00-16:00 in ICT 616

    Numerical computations using floating point arithmetic are affected by rounding errors leading to erroneous results and unstable computations. This is especially the case when the computations involve geometric objects.

    Geometric computations are frequently composed of simple sub-computations called geometric primitives. An example of a geometric primitive is thetest in two dimensions to check if a point is on one side, on or on the other side of an oriented line. If this test can be executed efficiently and without error then the convex hull of a two dimensional point set can also be computed exactly. The practical uses of such computation can be found for example in GIS systems. Since they involve extensive computations of geometric objects inconsistencies that occur due to instabilities in the geometric primitives can lead to failures of the systems that are very difficult to diagnose.

    In this talk we will explore interval arithmetic and a version of an exact computation as they can be implemented for geometric primitives.

  44. Optimal constructions for private function evaluation Saeed Sadeghian [University of Calgary, sadeghian(at)gmail.com] Friday March 30, 2012 at 15:00-16:00 in ICT 616

    In the problem of secure multi-party computation, there are n parties, where i-th party holds private input x_i, 1<=i<=n. The goal is for a subset (or all) of the parties to learn f(x_1,...,x_n) but nothing else. In some applications the function itself is proprietary and belongs to one of the parties who wants to keep it private. This variant of the problem is often referred to as "private function evaluation". There are two approaches to designing such protocols. First is to design general-purpose protocols which can be used for any function. Second is to take advantage of function structure to design more efficient customized protocol. We revisit the problem of designing general-purpose private function evaluation (PFE). In this talk I will talk about the two-party version of our protocol. An overview of our multi-party version will be given. Both solutions deviate from the traditional approach based on universal circuits and yield significantly more efficient constructions.

  45. How three parties establish a secret - elliptic curve pairings Monir Rad [University of Calgary, mrezaira(at)ucalgary.ca] Friday March 23, 2012 at 15:00-16:00 in ICT 616

    In the Diffie-Hellman protocol, two parties establish a common secret cryptographic key in one round of communication. The traditional Diffie-Hellman protocol can be extended to three parties where any pair of the three would have to establish a common key in one round, and pass the common keys to the third party in the second round. Now the question is: Is it possible to establish a three parties cryptographic key in one round by employing some additional arithmetic structure available for algebraic curves? This question has been answered positively by employing bilinear mappings, known as pairings. In this talk we present pairings on elliptic curves and discuss how it can be efficiently used to establish a secret among three parties.

  46. Applications of computer algebra to coding theory Jean-François Biasse [University of Calgary, biasse(at)lix.polytechnique.fr] Friday March 16, 2012 at 15:00-16:00 in ICT 616

    In this talk, we present applications of computer algebra to decoding algorithms of certain codes. The computer algebra algorithm we will study essentially rely on manipulations of matrices. They allow us to find generating elements with good properties for some sets. We will show how to use these algorithms for the purpose of decoding certain codes. A general framework was proposed by Guruswami that could be applied to some standard codes such as Reed-Solomon codes, or Algebraic-Geometric codes. We will follow this approach to achieve polynomial time decoding for a class of codes described by Lenstra and Guruswami for which decoding was still an open problem.

  47. How to efficiently select a leader using dice but no clock [PODC 2012] Philipp Woelfel [University of Calgary, woelfel(at)ucalgary.ca] Friday March 09, 2012 at 15:00-16:00 in ICT 616

    Consider a system with multiple processors which can only communicate with each other by reading and writing shared variables. The processors are asynchronous: they run with arbitrary and constantly changing speeds. In such systems, even seemingly simple tasks cannot be solved with deterministic algorithms. For example, there is no deterministic Leader Election protocol, in which exactly one of the participating processes returns "win" and all other ones return "lose". This is unfortunate, as Leader Election and its linearizable counter part, Test-and-Set, are fundamental synchronization primitives that have many algorithmic applications. Fortunately, randomization can be a way out of this dilemma. In this talk I will discuss recent progress in the design of time- and space- efficient randomized Leader Election algorithms. In particular, I will present a simple algorithm that solves the problem with an expected step complexity of O(log* n), improving on a previous O(loglog n) bound.

    Dice, clocks, or background in shared memory computing are not required. This is joint work with George Giakkoupis.

  48. Towards secure and reliable message transmission in information theoretic setting Rei Safavi-Naini [University of Calgary, rei.safavi(at)gmail.com] Friday March 02, 2012 at 15:00-16:00 in ICT 616

    We consider the problem of reliable and secure message transmission in two settings: noisy channel with an eavesdropping adversary, and a network setting where some of the network nodes are controlled by the adversary. We show how reliability and security can be formalized in these two settings and outline a general construction for a 1-round secure message transmission protocol for the network setting that provides provable reliability and perfect privacy. One of the main building blocks of this construction is list decodable codes that are used for providing reliability over noisy channels.

    The talk emphasizes the underlying concepts and provides all the required definitions.

  49. How to take the derivative of computations Jonathan Gallagher [University of Calgary, jdgallag(at)ucalgary.ca] Friday February 10, 2012 at 15:00-16:00 in ICT 616

    This talk explores models of computation in which every function has a differential. A concrete model in which it was possible to take the derivative of computations was first explored by Ehrhard in 2002. Since then, research has focused on a system, called the differential lambda calculus (DLC), and its semantics. Of particular interest has been its connection to a semantics for resource control and nondeterminism.

    In 2010, Manzonetto began to study models of the DLC which are also full models of computability. However, the only known models were degenerate in the sense that the addition was idempotent and it seemed plausible that all such models might have to be degenerate. If this were true, it would lead to a disappointing theory.

    In this talk, we will consider adding derivatives to more basic models of computability given by Turing categories and Partial Combinatory Algebras. We will make a key observation about the models of these systems that shows the model theory may be interesting after all. We will then sketch out the beginnings of constructing a non-degenerate model.

  50. Another look at the inversion over binary fields Kimmo Järvinen [Aalto University, kimmo.jarvinen(at)aalto.fi] Vassil Dimitrov [University of Calgary, dimitrov(at)enel.ucalgary.ca] Friday February 03, 2012 at 15:00-16:00 in ICT 616

    In this paper we are offering several optimization opportunities for implementing one of the most common operations in several public key cryptographic systems: the inversion over binary Galois fields. The optimizations are based on the combination between new inversion formulae and efficient use of the repeated squaring technique. Over some of the NIST recommended fields, our technique leads to the most economical---in terms of multiplications---inversion procedures. The main algorithm proposed is provably better than the Itoh-Tsujii algorithm for inversion. The inversion formulae proposed in this paper utilize better the advantages of the repeated squaring technique and offer additional computational savings in terms of the number of clock cycles used. The algorithms proposed are straightforwardly usable in both software and hardware implementations.

  51. RMR-efficient randomized abortable mutual exclusion Abhijeet Pareek [University of Calgary, abhijeet.ucalgary(at)gmail.com] Friday January 27, 2012 at 15:00-16:00 in ICT 616

    Mutual exclusion, also known as locking, is a fundamental and well studied problem in distributed computing. In this problem, N processes synchronize among themselves to access a Critical Section such that no two processes access the Critical Section at the same time. Recent research on mutual exclusion locks for the asynchronous shared-memory model has focused on local spin algorithms that use the remote memory references (RMRs) metric.

    Local spin mutual exclusion locks do not meet a critical demand of many systems. Specifically, the locks employed in database systems and in real time systems must support a "timeout" capability, that is, it must be possible for a process that waits "too long" to abort its attempt to acquire the lock. Locks that allow a process to abort its attempt to acquire the lock are called abortable mutual exclusion locks. Jayanti presented an efficient deterministic abortable mutual exclusion lock with worst-case O(log N) RMR complexity. The problem of designing a randomized abortable mutual exclusion algorithm with sublogarithmic expected RMRs has remained open. This talk will present a solution to this problem, where we will present a randomized abortable mutual exclusion lock with O(log N/log log N) expected RMRs.

  52. Rumor spreading and expansion properties of networks [STACS 2011] George Giakkoupis [University of Calgary, ggiakkou(at)ucalgary.ca] Friday December 02, 2011 at 14:00-15:00 in ICT 616

    The problem of spreading a piece of information, or rumor, from a single node to all the other nodes in a network is a fundamental one, with a variety of applications. A classic randomized algorithm for rumor spreading is that every node establishes a connection with a random neighbor in each round, and the two nodes exchange the rumors they have. The number of rounds that this algorithm needs to disseminate a rumor to all nodes has been studied extensively, for several network topologies. In this talk I will present some recent results that relate the number of rounds needed for an arbitrary network, with some standard measures of how ``well-connected'' this network is, namely, conductance and vertex expansion.

  53. Preserving quantum correlations may be good for the environment Jibran Rashid [University of Calgary, jrashid(at)cpsc.ucalgary.ca] Friday November 25, 2011 at 14:00-15:00 in ICT 616

    A ball thrown at a wall returns to its origin with velocity equal in magnitude but opposite in direction (in an ideal setup). In other words the direction or sign associated with the velocity in the beginning and at the end is anti-correlated. This is a direct consequence of the laws of physics which serve as guiding principles for deriving physical consequences such as the correlations above. The example may seem mundane given that such correlations are part of our every day experience. The intriguing nature of correlations produced by quantum physcics (known as nonlocality) however defies such an intuitive explanation.

    The talk will give an overview of recent work on obtaining strong nonlocal correlations from weaker correlation sources. The talk will appeal to a general audience by presenting emerging applications of the work in cryptography and quantum biology.

  54. Program correctness for multicore and multiprocessor machines Lisa Higham [University of Calgary, higham(at)ucalgary.ca] Friday November 18, 2011 at 14:00-15:00 in ICT 616

    Multiprocessor and multicore machines incorporate sophisticated hardware components such as write-buffers, multiple busses, layers of caches, and elaborate interconnect topologies to more effectively exploit the potential efficiency of many computational units. The result can be blisteringly fast computation---of something! The features that enhance speed are precisely the ones that make it extremely challenging to assert correctness. The output of a program can be very different from what the algorithm designer expected. Because such machines have only "weak memory consistency" there is no guarantee, for example, of Lamport's Sequential Consistency or database's Serializability.

    I will describe a modelling framework that helps us specify what guarantees such a machine does provide. Then I will illustrate its use by showing some possibility and impossibility results for familiar synchronization problems on a multiprocessor with X86-like architecture.

    This is an introductory talk. No familiarity with even the terms above is needed.

  55. Preventing sybil attacks by privilege attenuation: A design principle for social network systems [ESORICS 2009] [S&P 2011] Philip W. L. Fong [University of Calgary, pwlfong(at)ucalgary.ca] Friday November 04, 2011 at 14:00-15:00 in ICT 616

    In Facebook-style Social Network Systems (FSNSs), which are a generalization of the access control model of Facebook, an access control policy specifies a graph-theoretic relationship between the resource owner and resource accessor that must hold in the social graph in order for access to be granted. Pseudonymous identities may collude to alter the topology of the social graph and gain access that would otherwise be forbidden. We formalize Denning's Principle of Privilege Attenuation (POPA) as a run-time property, and demonstrate that it is a necessary and sufficient condition for preventing the above form of Sybil attacks. A static policy analysis is then devised for verifying that an FSNS is POPA compliant (and thus Sybil free). The static analysis is proven to be both sound and complete.

  56. Key establishment in a quantum world [CRYPTO 2011] [Paper] Peter Høyer [University of Calgary, hoyer(at)ucalgary.ca] Friday October 28, 2011 at 14:00-15:00 in ICT 616

    In 1974, Ralph Merkle proposed the first unclassified scheme for secure communications over insecure channels. When legitimate communicating parties are willing to spend an amount of computational effort proportional to some parameter N, an eavesdropper cannot break into their communication without spending a time proportional to N^2, which is quadratically more than the legitimate effort. We showed in an earlier paper that Merkle's schemes are completely insecure against a quantum adversary, but that their security can be partially restored if the legitimate parties are also allowed to use quantum computation: the eavesdropper needed to spend a time proportional to N^{3/2} to break our earlier quantum scheme. Furthermore, all previous classical schemes could be broken completely by the onslaught of a quantum eavesdropper and we conjectured that this is unavoidable.

    We give two novel key establishment schemes in the spirit of Merkle's. The first one can be broken by a quantum adversary that makes an effort proportional to N^{5/3} to implement a quantum random walk in a Johnson graph reminiscent of Andris Ambainis' quantum algorithm for the element distinctness problem. This attack is optimal up to logarithmic factors. Our second scheme is purely classical, yet it cannot be broken by a quantum eavesdropper who is only willing to expend effort proportional to that of the legitimate parties.

    NO prior knowledge of quantum computing will be assumed.

  57. The life and work of Alan M. Turing Jonathan P. Sorenson [Butler University, jsorenso(at)butler.edu] Friday October 21, 2011 at 14:00-15:00 in ICT 516

    In the 1930s, the British mathematician Alan Turing developed a mathematical model of computation, now called the Turing Machine, which has encouraged many to give him credit for the invention of the computer as we know it today. Turing is perhaps best known for his contributions in breaking the Enigma cipher of the German military during World War II. He was also a pioneer in artificial intelligence and neural networks, and today the Turing Award serves as the computer scientist's version of the Nobel Prize.

    Alan Turing was arrested for homosexuality in 1952 and forced to undergo hormone treatments; it is believed this led to his suicide by cyanide poisoning at the age of 42 in 1954. In this talk we will look at Turing's work, and discuss some of the controversies surrounding his life.

  58. Oblivious DFA evaluation and its applications [EPRINT] [CT-RSA 2012] Payman Mohassel [University of Calgary, pmohasse(at)cpsc.ucalgary.ca] Friday October 14, 2011 at 14:00-15:00 in ICT 616

    First, I will briefly introduce secure two-party computation (2PC), an interesting area of cryptography. Then, I will focus on a specific instance of secure 2PC, i.e. oblivious Automata evaluation. Oblivious Automata evaluation allows two parties (a client who holds an input string X and a server who holds an Automata G) to learn the result of evaluating G on X but nothing else. I will describe a simple and efficient, secure two-party construction for this problem. If there is time, I will also outline some applications of our construction to secure pattern matching and intrusion detection.

  59. (Hyper-)elliptic curve cryptography Renate Scheidler [University of Calgary, rscheidl(at)ucalgary.ca] Friday October 07, 2011 at 14:00-15:00 in ICT 616

    This survey talk provides an overview of elliptic and hyperelliptic curves in the context of their use in discrete logarithm based cryptography. After introducing the cryptographic key agreement problem and one of its major solutions, the celebrated Diffie-Hellman key establishment protocol, we give an overview of elliptic curves and their group law. We then move on to hyperelliptic curves and their associated group (the Jacobian), describing a representation of group elements as well as the group operation. If time permits, we will briefly summarize methods for extracting discrete logarithms on both elliptic and hyperelliptic curves, and touch on alternative curve models. The talk is targeted at an audience with no or minimal exposure to cryptography and no prior knowledge of algebraic curves.

  60. Implementing one-shot timestamps from shared registers [PODC 2011] Maryam Helmi [University of Calgary, mhelmikh(at)ucalgary.ca] Friday September 30, 2011 at 14:00-15:00 in ICT 616

    In asynchronous shared memory systems, processes communicate by reading and by writing to shared registers. Such operations are called events, and it is in general impossible for processes to determine the exact order of all events in an execution. A time stamp object allows processes to obtain some information about the ordering of events. Time stamps have many applications, including in cache coherency protocols and to achieve fairness (e.g., first-come first-served) in scheduling algorithms. I will present tight bounds for the space complexity of one-shot time stamp objects.

    Based on joint work with Lisa Higham, Eduardo Pacheco and Philipp Woelfel. Presented at PODC 2011.

  61. Is perfect randomness inherent for cryptography? Mohsen Alimomeni [University of Calgary, malimome(at)ucalgary.ca] Friday September 23, 2011 at 14:00-15:00 in ICT 616

    Randomness is essential in many areas of computer science specifically in cryptography (for example to generate secret keys). We always assume that we have access to perfect randomness (unbiased independently generated random bits) but this is not a realistic assumption. Our sources of randomness (such as radioactive decay, thermal noise and weather) does not output perfect randomness. We want to understand if we can base our primitives on more practical assumption of having only imperfect random sources. In other words, for a particular primitive, is perfect randomness inherent? or we can modify it to tolerate imperfect randomness. In this talk, a classification of random sources based on their feasibility for a few cryptographic primitives is given.

  62. The rope men of Tibet: A puzzle from linear logic! Matvey Soloviev [University of Cambridge, UK, ms900(at)hermes.cam.ac.uk] Friday September 16, 2011 at 14:00-15:00 in ICT 616

    Sometimes rather abstract problems -- like the complexity of determining the equality of maps in a linearly distributive category -- can be expressed as easy to explain puzzles. The internet then allows one to crowdsource such problems ... reducing one's work load!

    The talk will explain the puzzle (in parts) and hopefully get you playing. The talk will try to avoid explaining the scientific significance of the puzzle. A solution to an interesting subproblem, which involves rope men in Tibet, will be explored.

http://www.cpsc.ucalgary.ca/~hoyer/