Date( Fall 2009 ) Category Seminar Info 2009/12/02 CQIL - Cryptography and Quantum Information Place: McConnnell 103 Time: 11:30 - 12:30 Speaker: Pranab Sen Affiliation: Tata Institute of Fundamental Research Title: k-Copy Quantum Expanders Nearly Meeting the Ramanujan Bound (Part II) Abstract: A k-copy quantum expander is a small set of unitary operators such that the superoperator consisting of choosing a random unitary from the set and applying k independent copies of it is close to the ideal superoperator consisting of choosing a random unitary from the Haar measure and applying k independent copies of it. k-copy quantum expanders give a way of constructing approximate k-designs of unitaries, and are an analogue of approximate k-wise independence in the quantum world. The well-known expanders of computer science turn out to be 1-copy expanders. A k-copy expander consisting of D unitaries cannot be closer than \Omega(D^{-1/2}) to the ideal superoperator in the spectral norm on linear operators, in what is known as the Ramanujan bound. No explicit construction of even 1-copy quantum expanders was known earlier, that was provably close to the Ramanujan bound. In this work, we give an explicit construction of k-copy quantum expanders that have distance c_k D^{-1/2 + o(1)} to the ideal superoperator, where c_k is a constant depending on k. This leads to better constructions of approximate k-designs of unitaries. Our construction is a quantum analogue of a construction of classical 1-copy expanders by Ben-Aroya and Ta-Shma, which in turn was a generalisation of a combinatorial construction called zig-zag graph product by Reingold, Vadhan and Wigderson. 2009/11/27 CQIL - Cryptography and Quantum Information Place: McConnell 103 Time: 11:30 - 12:30 Speaker: Benoit Collins Affiliation: University of Ottawa Title: Free probability and quantum information theory Abstract: After reviewing a few notions of free probability, I will explain how it can be used to refine our understanding of the behavior of the collection of eigenvalues of output states of quantum channels chosen at random. I will also explain the applications to the entropy additivity problems. This is joint work with Ion Nechita. Seminar co-sponsored by the MITACS Quantum Information Processing program. 2009/11/25 CQIL - Cryptography and Quantum Information Place: McConnell 103 Time: 11:30 - 12:30 Speaker: Pranab Sen Affiliation: Tata Institute Title: k-Copy Quantum Expanders Nearly Meeting the Ramanujan Bound Abstract: A k-copy quantum expander is a small set of unitary operators such that the superoperator consisting of choosing a random unitary from the set and applying k independent copies of it is close to the ideal superoperator consisting of choosing a random unitary from the Haar measure and applying k independent copies of it. k-copy quantum expanders give a way of constructing approximate k-designs of unitaries, and are an analogue of approximate k-wise independence in the quantum world. The well-known expanders of computer science turn out to be 1-copy expanders. A k-copy expander consisting of D unitaries cannot be closer than \Omega(D^{-1/2}) to the ideal superoperator in the spectral norm on linear operators, in what is known as the Ramanujan bound. No explicit construction of even 1-copy quantum expanders was known earlier, that was provably close to the Ramanujan bound. In this work, we give an explicit construction of k-copy quantum expanders that have distance c_k D^{-1/2 + o(1)} to the ideal superoperator, where c_k is a constant depending on k. This leads to better constructions of approximate k-designs of unitaries. Our construction is a quantum analogue of a construction of classical 1-copy expanders by Ben-Aroya and Ta-Shma, which in turn was a generalisation of a combinatorial construction called zig-zag graph product by Reingold, Vadhan and Wigderson. 2009/11/20 General Place: MC103 Time: 11:00 - 12:30 Speaker: Peter Marbach Affiliation: University of Toronto Area: Networks Title: Online Social Networks: Research Challenges and some Results Abstract: Online social networks have revolutionized the way we interact and share information over the Internet. Popular social networking applications include YouTube, Flickr, MySpace, Facebook, and Twitter, which support millions of active users. While being enormously popular, these applications only scratch the surface of what is possible to do, and there are tremendous opportunities in developing new, more advanced online social networking applications. Creating such applications poses new and fascinating research problems. One of major research challenges in this domain is to develop a formal understanding of online social networks both in terms of how online social networks are formed, and how they can be used to efficiently share and distribute information. In the talk, we will discuss research aiming at creating a mathematical foundation of online social networks that provides a formal understanding and framework for the design and analysis of algorithms for online social networking applications. The first part of the talk will present a broader research agenda for online social network. The second part will focus on recent theoretical results on search algorithms in online social networks. An interesting aspect of the results that we obtain is that they provide insight into why real-life social networks are so efficient. Biography of Speaker: Peter Marbach was born in Lucerne, Switzerland. He received the Eidg. Dipl. El.-Ing. (1993) from the ETH Zurich, Switzerland, the M.S. (1994) in electrical engineering from the Columbia University, NY, U.S.A, and the Ph.D. (1998) in electrical engineering from the Massachusetts Institute of Technology (MIT), Cambridge, Massachusetts, U.S.A. He was appointed as assistant professor in 2000, and associate professor in 2005, at the Department of Computer Science of the University of Toronto. He has also been a visiting professor at Microsoft Research, Cambridge, UK, at the Ecole Polytechnique Federal at Lausanne (EPFL), Switzerland, and at the Ecole Normale Superieure, Paris, France, and a post-doctoral fellow at Cambridge University, UK. Peter Marbach has received the IEEE INFOCOM 2002 Best Paper Award for his paper "Priority Service and Max-Min Fairness". He is on the editorial board of the ACM/IEEE Transactions of Networking. His research interests are in the fields of communication networks, in particular in the area of wireless networks, peer-to-peer networks, and online social networks. 2009/11/16 DMO - Discrete Mathematics and Optimization Place: Burnside 1205 Time: 16:30 - 17:30 Speaker: Christophe Weibel Affiliation: McGill University Title: Flow-Cut Gaps for Integer and Fractional Multiflows Abstract: Consider a routing problem instance consisting of a supply graph G=(V,E (G)) and a demand graph H=(V,E(H)). If the pair obeys the cut condition, then the flow-cut gap for this instance is the minimum value C such that there exists a feasible multiflow for H if each edge of G is given capacity C. It is well-known that the flow-cut gap may be greater than 1 even in the case where G is the (series-parallel) graph K2,3. The subject of this talk is the "integer" flow-cut gap. What is the minimum value C such that there exists a feasible integer valued multiflow for H if each edge of G is given capacity C? We study the case of series-parallel graphs. Let G be obtained by series-parallel operations starting from an edge st, and consider orienting all edges in G in the direction from s to t. A demand is compliant if its endpoints are joined by a directed path in the resulting oriented graph. We show that if the cut condition holds for a compliant instance and G+H is Eulerian, then an integral routing of H exists. This result includes, as a special case, routing on a ring, but is not a special case of the Okamura-Seymour theorem. We use this to prove that the integer flow-cut gap in series-parallel graphs is 5. 2009/11/11 CQIL - Cryptography and Quantum Information Place: McConnell 103 Time: 11:30 - 12:30 Speaker: Steve Flammia Affiliation: Perimeter Institute for Theoretical Physics Title: Ultra Fast Quantum State Tomography Abstract: Everybody hates tomography. And with good reason! Experimentalists hate it because it is inefficient and difficult. Theorists hate it because it isn't very "quantum." But because of our current lack of meso-scale quantum computers capable of convincingly performing non-classical calculations, tomography seems like a necessary evil. In this talk, I will attempt to banish quantum state tomography to the Hell of Lost Paradigms where it belongs. I hope to achieve this by introducing several methods for learning quantum states more efficiently, in some cases exponentially so. The first method runs in polynomial time and outputs a polynomial-sized classical approximation of the state (in matrix product state form), together with a rigorous bound on the fidelity. The second result takes advantage of the fact that most interesting states are close to pure states to get a quadratic speedup using ideas from compressed sensing. I'll also show simulations of these methods that demonstrate how well they work in practical situations. Both of these results are heralded, and require no a priori assumptions about the state. This is joint work with S. Bartlett, D. Gross, R. Somma (first result), and D. Gross, Y.-K. Liu, S. Becker, J. Eisert, (second result; arXiv:0909:3304). Seminar sponsored by the MITACS Quantum Information Processing program. 2009/11/09 Algorithms Place: Burnside 1205 Time: 16:30 - 17:30 Speaker: Juan Vera Affiliation: Waterloo Title: Positive Polynomials Over Equality Constrained unbounded Sets Abstract: A simple yet powerful algebraic connection between the set of polynomials that are non-negative on a given closed domain and the set of polynomials that are non-negative on the intersection of the same domain and the zero set of a given polynomial is presented. This connection has interesting theoretical as well as algorithmic implications. It yields a succinct derivation of copositive programming reformulations for a big class of programs, generalizing Burer's copositive formulation for mixed non-convex quadratically constrained quadratic programming problems. As corollary of our main theorem we also obtain representation theorems for positive polynomials on closed sets. To illustrate the results we show how to use Polynomial Programming as a general framework for conic relaxations. This framework is used to re-derive previous relaxation schemes and provide stronger ones for general binary quadratic optimization. In particular, second-order cone relaxations are proposed. Computational tests show that using the second-order cone relaxation with triangle inequalities provides a bound that is competitive with the semidefinite bound strengthened with triangle inequalities but the former relaxation is computationally more efficient. This is joint work with Javier Pena and Luis Zuluaga, and Bissan Ghaddar and Miguel Anjos. 2009/11/04 CQIL - Cryptography and Quantum Information Place: McConnell 103 Time: 11:30 - 12:30 Speaker: Mathieu Cliche Affiliation: University of Waterloo Area: Quantum information Title: A relativistic quantum channel that can extract entanglement from the vacuum Abstract: We model a relativistic quantum channel in which Alice and Bob are Unruh-DeWitt detectors for scalar quanta and the only noise in their communication is due to quantum fluctuations. We calculate the classical channel capacity as a function of the spacetime separation and we confirm that the classical as well as the quantum channel capacity are strictly zero for spacelike separations. We show that this channel can be used to entangle Alice and Bob instantaneously. Alice and Bob are shown to extract this entanglement from the vacuum through a Casimir-Polder effect. 2009/10/20 CQIL - Cryptography and Quantum Information Place: McConnell 103 Time: 17:00 - 18:00 Speaker: Min-Hsiu Hsieh Affiliation: Erato-SORST Title: Performance of Entanglement-assisted Quantum LDPC Codes Constructed From Finite Geometries Abstract: We investigate the performance of entanglement-assisted quantum low-density parity-check (LDPC) codes constructed from finite geometries. Though the entanglement-assisted formalism provides a universal connection between a classical linear quaternary code and an entanglement-assisted quantum error-correcting code (EAQECC), the issue of maintaining large amount of pure maximally entangled states in constructing EAQECCs is a practical obstacle to its use. We provide families of EAQECCs with an entanglement consumption rate that decreases exponentially. Surprisingly, these EAQECCs outperform those codes constructed earlier. Based on joint work with Wen-Tai Yen and Li-Yi Hsu. The paper is available at arXiv:0906.5532 2009/10/19 DMO - Discrete Mathematics and Optimization Place: Burnside 1205 Time: 16:30 - 17:30 Speaker: Gyula Pap Affiliation: Cornell University Title: Algorithms for integral and half-integral multiflows Abstract: A classical problem in combinatorial optimization is that of maximum multiflows. We are given an undirected graph G=(V,E), and a set of terminals A subset of V. A multiflow is defined as a set of |A|(|A|-1)/ 2 flows between all pairs of distinct terminals. The goal is to maximize the total size of the multiflow, that is the sum of the size of all the |A|(|A|-1)/2 flows, subject to certain capacity constraints. Variations of the problem arise from edge- or node- capacities, and/or adding a (half-)integrality constraint. The problem is really interesting even for the special case of all-one node capacities, which is characterized by Mader's min-max formula, and solved by Lovász' linear matroid matching algorithm. Mader's formula also applies for arbitrary capacities, but matroid matching, in the obvious way of expanding the graph, only implies an exponential time algorithm. The main result presented in this talk is a strongly polynomial time algorithm to find a maximum integral multiflow subject to node- capacities (the most general of all these variations). This improves on a result of Ibaraki, Karzanov and Nagamochi for the edge- capacitated, half-integral version, and on Keijsper, Pendavingh and Stougie's weakly polynomial time algorithm for the edge-capacitated, integral version. These results are generalized to the node- capacitated version, although using completely different tehniques. The half-integral node-capacitated multiflow problem is solved based on a recent result saying that the polytope of shortest maximum multiflows is half-integral, which implies a strongly polynomial algorithm via ellipsoid method and Frank and Tardos' diophantine approximation. To solve the integral node-capacitated multiflow problem, we first solve it to half-integrality, and then use a scaling- type argument motivated by Gerards' proximity lemma for b-matching to reduce the problem to small capacities. In the presentation we will also take a look at related results and techniques, such as a splitting-off algorithm for Lov\'asz' and Cherkassky's result, a divide-and-conquer-type argument for the edge-capacitated version. 2009/10/19 General Place: MC320 Time: 11:00 - 12:00 Speaker: Patrick Lam Affiliation: Assistant Prof at Waterloo Area: Data Structures Title: Implementation and Use of Data Structures in Java Programs Abstract: Programs manipulate data. For many classes of programs, this data is organized into data structures. Java's standard libraries include robust, general-purpose data structure implementations; however, standard implementations may not meet developers' needs, forcing them to implement ad-hoc data structures. We investigate the implementation and use of data structures in practice by developing a tool to statically analyze Java libraries and applications. Our DSFinder tool reports 1) the number of likely and possible data structure implementations in a program and 2) characteristics of the program's uses of data structures. We applied our tool to 62 open-source Java programs and manually classified possible data structures. We found that 1) developers overwhelmingly used Java data structures over ad-hoc data structures; 2) applications and libraries confine data structure implementation code to small portions of a software project; and 3) the number of ad-hoc data structures correlates with the number of classes in both applications and libraries, with approximately 0.020 data structures per class. This is joint work with Syed Albiz, submitted to ICSE 2010. Biography of Speaker: Patrick was a B.Sc. and M.Sc. student at McGill. He then did his Ph.D. at MIT with Martin Rinard and then a post-doc back at McGill. He is currently an Assistant Prof at Waterloo. 2009/10/14 CQIL - Cryptography and Quantum Information Place: McConnell 103 Time: 11:30 - 12:30 Speaker: Jérémie Roland Affiliation: NEC Laboratories (Princeton) Title: Adiabatic quantum optimization fails for random instances of NP-complete problems Abstract: Adiabatic quantum optimization has attracted a lot of attention because small scale simulations gave hope that it would allow to solve NP-complete problems efficiently. Later, negative results proved the existence of specifically designed hard instances where adiabatic optimization requires exponential time. In spite of this, there was still hope that this would not happen for random instances of NP-complete problems. This is an important issue since random instances are a good model for hard instances that can not be solved by current classical solvers, for which an efficient quantum algorithm would therefore be desirable. Here, we will show that because of a phenomenon similar to Anderson localization, an exponentially small eigenvalue gap appears in the spectrum of the adiabatic Hamiltonian for large random instances, very close to the end of the algorithm. This implies that unfortunately, adiabatic quantum optimization also fails for these instances by getting stuck in a local minimum, unless the computation is exponentially long. Joint work with Boris Altshuler and Hari Krovi. 2009/10/07 CIM - Centre for Intelligent Machines Place: McConnell 437 Time: 11:30 - 12:30 Speaker: Davd W. Cofer Affiliation: Georgia State University Title: ANIMATLAB: A PHYSICS BASED 3-D GRAPHICS ENVIRONMENT FOR BEHAVIORAL NEUROBIOLOGY RESEARCH Abstract: Understanding neural mechanisms of behavior has frequently depended on comparisons between detailed descriptions of freely behaving animals and fictive motor programs displayed by neurons in anesthetized, restrained, and dissected preparations. We have developed a software toolkit, AnimatLab, to help researchers determine whether their descriptions of neural circuit function can account for how specific patterns of behavior are controlled. AnimatLab enables one to build a virtual body from simple LEGO™-like building blocks, situate it in a virtual 3-D world subject to the laws of physics, and control it with a multi-cellular, multi-compartment neural circuit model. A Body Editor enables adjustable blocks, balls, truncated cones, cylinders and meshes to be connected through a variety of joints to form a body. Sensors enable extrinsic and intrinsic signals to be detected, and virtual muscles governed by Hill muscle models span the joints to produce movement. The physics engine Vortex™ from CM-Labs simulates gravity, buoyancy, drag, friction, contact collision, and muscle tension for the various body parts. A Neural Editor enables a neural network to be constructed from a menu of neurons and synapses, and then linked to sensors and effectors on the body. We are currently using AnimatLab to study the neural control of locomotion and arm movements, the escape behavior of crayfish, and jumping in locust. In the near future we plan to expand AnimatLab so it can be used to build and test biomimetic robots. 2009/10/07 CQIL - Cryptography and Quantum Information Place: McConnell 103 Time: 11:30 - 12:30 Speaker: Artem Kaznatcheev Affiliation: McGill University Title: Properties of unitary t-designs Abstract: Unitary t-designs provide a method to simplify integrating polynomials of degree less than t over U(d). Designs allows us to replace the average over U(d) (an integral) by an average over the design (a finite sum). We prove the trace double sum inequality and use it to provide a metric definition of designs. The new definition provides an easier way of checking in a set of unitaries forms a design. In the search for small designs, we classify minimal designs according to their weight function. As an alternative approach to deriving lower bounds on the size of t-designs, we introduce a greedy ‘algorithm’ for constructing designs. We provide a construction for minimum 1-designs based on orthonormal bases of the space of d-by-d matrices. The constructions provides a simple way to evaluate the average of U*V*UV for fixed V. This allows us to prove that t-designs are non-commuting sets, supporting our intuition that the elements of a design are well ‘spread out’. 2009/10/05 Algorithms Place: Burnside 1205 Time: 16:30 - 17:30 Speaker: Deeparnab Chakrabarty Affiliation: University of Waterloo Title: Two generalizations of (0,1)-covering problems Abstract: Pick your favorite (set) covering problem: for the purpose of this talk consider the line-cover problem of covering a set of points on a line by line segments. We call a covering problem (0,1) if any set covers any element at most once. This terminology arises from casting this problem as a covering integer program (CIP) where the constraint matrix is {0,1}. We consider two generalizations of a (0,1) covering problem. In each generalization, we associate an integral supply for each set (column of the CIP matrix) and a demand for each element (row of the CIP matrix). In the first problem, called the column-restricted covering problem, we need to choose a minimum cost family of sets such that for each element the total supply of the sets chosen exceeds the demand of the element. The second problem, which we call the priority covering problem, is another (0,1) covering problem obtained as follows. We say a set covers an element iff it contains it and the supply of the set is larger than the demand of the element. Given this new set system, we want to choose a standard set cover, the minimum cost family of sets which covers every element at least once. We are interested in connecting the approximability, and in particular the integrality gaps of the corresponding CIPs, of these generalized problems to that of the original (0,1) problem. In this talk, we will describe some partial progress we've made. In particular, we show that for the line cover problem the integrality gaps of both are within a constant factor of the original one's. Joint work with Elyot Grant and Jochen Konemann 2009/09/30 CQIL - Cryptography and Quantum Information Place: McConnell 103 Time: 11:30 - 12:30 Speaker: Ion Nechita Affiliation: University of Ottawa Title: Eigenvalue statistics for products of random quantum channels Abstract: We study products of random quantum channels from the point of view of random matrix theory. Two models are considered: independent and conjugate channels. The second model has been very successful in quantum information theory as a source for counter examples to some famous additivity conjectures. We show how the two models relate and we compute average traces of outputs of such random channels. Our main tool is a graphical calculus for random matrices developed by the authors. This calculus is based on a diagrammatic notation for tensors, inspired by ideas of Penrose and Coecke. Then, interpreting Weingarten calculus in our formalism, we describe a method for computing expectation values of diagrams which contain Haar-distributed random unitary matrices. This is done by the means of a graph-expansion of the original diagram. The graphical computations are intuitive and give insight on the dominating terms. Finally, applications of these results to additivity conjectures are discussed. This is joint work with Benoît Collins (University of Ottawa). 2009/09/16 CQIL - Cryptography and Quantum Information Place: McConnell 103 Time: 11:30 - 12:30 Speaker: Kazuo Iwama Affiliation: Kyoto University Area: Quantum Information Title: Quantum Counterfeit Coin Problems Abstract: The counterfeit coin problem is a well-known puzzle whose origin dates back to 1945; in the American Mathematical Monthly, 52, p.~46, E. Schell posed the following question which is probably one of the oldest questions about the complexity of algorithms: You have eight similar coins and a beam balance. At most one coin is counterfeit and hence underweight. How can you detect whether there is an underweight coin, and if so, which one, using the balance only twice?'' The puzzle immediately fascinated many people and since then there have been several different versions and extensions in the literature. In this talk, we study the quantum query complexity for this problem. We assume that the balance scale gives us only balanced'' or tilted'' information and that we know the number $k$ of false coins in advance. The balance scale can be modeled by a certain type of oracle and its query complexity is a measure for the cost of weighing algorithms (the number of weighings). Let $Q(k,N)$ be the quantum query complexity of finding all $k$ false coins from the $N$ given coins. We show that for any $k$ and $N$ such that $k < N/2$, $Q(k,N)=O(k^{1/4})$, contrasting with the classical query complexity, $\Omega(k\log(N/k))$, that depends on $N$. Some bounds for small $k$ are also investigated: (i) $Q(1,N)=1$, (ii) $Q(2,N)=1$, and (iii) $2\leq Q(3,N) \leq 3$. Biography of Speaker: Professor Iwama received the B.E., M.E. and Ph.D. degrees from Department of Electrical Engineering, Kyoto University in 1973, 1975 and 1980, respectively. His reseach interets are mainly algorithms and complexity theory.