Skip to content. Skip to navigation
McGill Home SOCS Home
Personal tools
You are here: Home Announcements and Events Seminars Seminar History

Seminar Home
Fall 2014 Schedule
Winter 2015 Schedule
Summer 2015 Schedule
Archives

Date
( Summer 2010 )
Category Seminar Info
2009/07/17 CQIL - Cryptography and Quantum Information Place: McConnell 103
Time: 11:00 - 12:00
Speaker: Mark Wilde
Affiliation: Science Applications International Corp.
Title: Trading classical communication, quantum communication, and entanglement in quantum Shannon theory
Abstract: We give optimal trade-offs between classical communication, quantum communication, and entanglement for processing information in the Shannon-theoretic setting. We first prove a "unit-resource" capacity theorem that applies to the scenario where only the above three noiseless resources are available for consumption or generation. The optimal strategy mixes the three fundamental protocols of teleportation, super-dense coding, and entanglement distribution. Furthermore, no protocol other than these three fundamental ones is necessary to generate the unit resource capacity region. We then prove the "direct static" capacity theorem that applies to the scenario where a large number of copies of a noisy bipartite state are available (in addition to consumption or generation of the above three noiseless resources). The result is that a coding strategy involving the classically-assisted mother protocol and the three fundamental protocols is optimal. We finally prove the "direct dynamic" capacity theorem. This theorem applies to the scenario where a large number of uses of a noisy quantum channel are available in addition to the consumption or generation of the three noiseless resources. The optimal strategy combines the classically-enhanced father protocol with the three fundamental unit protocols. Interestingly, one octant of the direct-dynamic capacity region applies to an open question concerning the use of entanglement-assisted coding and teleportation for entanglement- and classically-assisted quantum communication. Biography of Speaker:

Mark M. Wilde holds the Ph.D. degree in Electrical Engineering from the University of Southern California with a special focus in quantum computing and communication. He also holds the M.S. degree in Electrical Engineering from Tulane University and the B.S. degree in Computer Engineering from Texas A&M University. He has published over 20 articles on the theory of quantum computing and communication and has presented talks at several quantum information conferences including the recent Theory of Quantum Computation, Communication, and Cryptography Workshop held in May 2009 in Waterloo, Canada. He will be teaching an introductory graduate course on the theory of quantum communication (quantum Shannon theory) at George Washington University in Washington, DC in the Fall of 2009.


2009/07/14 CQIL - Cryptography and Quantum Information Place: McConnell 103
Time: 11:00 - 12:00
Speaker: Mark Wilde
Affiliation: Science Applications International Corp.
Title: Quantum Shift Register Circuits
Abstract: A quantum shift register circuit acts on a set of input qubits and memory qubits, outputs a set of output qubits and updated memory qubits, and feeds the memory back into the device for the next cycle (similar to the operation of a classical shift register). Such a device finds application as an encoding and decoding circuit for a particular type of quantum error-correcting code, called a quantum convolutional code. Building on the Ollivier-Tillich and Grassl-Roetteler encoding algorithms for quantum convolutional codes, I present a method to determine a quantum shift register encoding circuit for a quantum convolutional code. I also determine a formula for the amount of memory that a CSS quantum convolutional code requires. I then detail primitive quantum shift register circuits that realize all of the finite- and infinite-depth transformations in the shift-invariant Clifford group (the class of transformations important for encoding and decoding quantum convolutional codes). The memory formula for a CSS quantum convolutional code then immediately leads to a formula for the memory required by a CSS entanglement-assisted quantum convolutional code. Biography of Speaker:

Mark M. Wilde holds the Ph.D. degree in Electrical Engineering from the University of Southern California with a special focus in quantum computing and communication. He also holds the M.S. degree in Electrical Engineering from Tulane University and the B.S. degree in Computer Engineering from Texas A&M University. He has published over 20 articles on the theory of quantum computing and communication and has presented talks at several quantum information conferences including the recent Theory of Quantum Computation, Communication, and Cryptography Workshop held in May 2009 in Waterloo, Canada. He will be teaching an introductory graduate course on the theory of quantum communication (quantum Shannon theory) at George Washington University in Washington, DC in the Fall of 2009.


2009/07/10 Faculty Candidate Talk Place: ENGMC 437
Time: 10:00 - 11:00
Speaker: Wenbo He
Affiliation:
Title: Privacy-Preserving Data Aggregation over Participatory Networks
Abstract: The emerging participatory networked embedded systems, designed for aggregated information collection with fine-granularity, are viewed as new generation of pervasive computing systems. We expect both social and economic impact of participatory networks. Applications of participatory networks are likely to deal with highly sensitive or private information. Hence, one of the pressing concerns of users is the confidentiality of the data collected about them. Therefore, we need a way to collect aggregated information while at the same time preserve data privacy. In this talk, I will present two privacy-preserving data aggregation schemes for additive aggregation functions. The first scheme, Cluster-based Private Data Aggregation (CPDA), leverages clustering protocol and algebraic properties of polynomials. It has the advantage of incurring less communication overhead. The second scheme, Slice-Mix-AggRegaTe (SMART), builds on slicing techniques and the associative property of addition. It has the advantage of incurring less computation overhead. The goal of this work is to bridge the gap between collaborative data collection and privacy preservation of individual data. I assess the two schemes by privacy-preservation efficacy, communication overhead, and data aggregation accuracy. Then we study the possibilities to achieve privacy preservation and integrity protection simultaneously. Finally, I will conclude this talk by discussing my future plan. Biography of Speaker:

Assistant professor in CS department at University of New Mexico starting in Fall 2008. Graduated from MONET Group directed by Professor Klara Nahrstedt at University of Illinois at Urbana-Champaign.


2009/06/15 DMO - Discrete Mathematics and Optimization Place: MC320
Time: 16:00 - 17:00
Speaker: Vahab Mirrokni
Affiliation: Google
Title: Submodular Maximization applied to Marketing over Social Networks
Abstract:

Submodular maximization is a central problem in optimization with several applications. Unlike minimizing submodular functions, submodular maximization is NP-hard. In this talk, we first describe recent approximation algorithms for this problem, and then discuss an application in optimal marketing over social networks. We give the first constant-factor approximation algorithms for maximizing non-negative submodular functions with multiple budget and matroid constraints. In particular, we give a randomized 2/5- approximation algorithm for maximizing non-negative submodular functions and a 1/5-approximatin for maximizingsubmodular functions with multiple budget constraints. Furthermore, we prove that achieving an approximation factor better than 1/2 requires exponential time.

In the second half of the talk, I will discuss an application in marketing digital goods over social networks, and study revenue- maximizing marketing strategies in the presence of positive network externalities of buyers. In particular, we study a set of influence- and-exploit marketing strategies and show how to use submodualr maximization to identify a set of influential buyers in a social network.

This talk is based on joint work with Feige and Vondrak (FOCS 2007), Hartline and Sundararajan (WWW 2008), and Lee, Nagarajan, Sviridenko (STOC 2009).

Biography of Speaker:

Vahab Mirrokni is a Senior Research Scientist at Google Research in New York. He joined Google after receiving a B.Sc. from Sharif University in 2001 and a Ph.D. from MIT in 2005, one year at MIT and Amazon.com, and two years at Microsoft Research. Vahab is co-winner of the SODA 2005 best student paper award and the ACM EC 2008 best paper award. He has published more than 55 papers in journals and conferences and has filed 12 patents in these areas. Vahab's research interests include algorithmic game theory, approximation algorithms, and the Internet Economics. At Google, he is working on various algorithmic and economic problems related to the Internet search and online advertisement.


2009/06/01 CQIL - Cryptography and Quantum Information Place: McConnell 103
Time: 10:00 - 11:00
Speaker: Francois Le Gall
Affiliation: ERATO-SORST
Title: Perfect Quantum Network Coding with Free Classical Communication
Abstract:

I will talk about the problem of efficiently transmitting quantum states through a network. It has been known for some time that without additional assumptions it is impossible to achieve this task perfectly in general --- indeed, it is impossible even for the simple butterfly network. In this work, as additional resource free classical communication between any pair of network nodes is allowed. I will show that perfect quantum network coding is achievable in this model whenever classical network coding is possible over the same network when replacing all quantum capacities by classical capacities.

This is a joint work with Hirotada Kobayashi, Harumichi Nishimura and Martin Roetteler. A preliminary version of the results can be found here.


2009/05/20 CQIL - Cryptography and Quantum Information Place: MC103
Time: 10:30 - 11:30
Speaker: Nicolas Dutil
Affiliation: McGill University
Title: Multiparty state merging and applications
Abstract: