[quantum-info] PIQuDos seminar on Wed Feb 12: Penghui Yao

[Gus Gutoski]

Please join us on Wednesday, February 12 at 4pm in the Time room for a
quantum information seminar by Penghui Yao.

Title: *Applications of Information Theory in Direct Sum and Direct Product
Problems*
Speaker: *Penghui Yao* (Centre for Quantum Technologies, National
University of Singapore)

Abstract: A fundamental question in complexity theory is how much resource
is needed to solve k independent instances of a problem compared to the
resource required to solve one instance. Suppose solving one instance of a
problem with probability of correctness p, we require c units of some
resource in a given model of computation. A direct sum theorem states that
in order to compute k independent instances of a problem, it requires k
times units of the resource needed to compute one instance. A strong direct
product theorem states that, with o(k * c) units of the resource, one can
only compute all the k instances correctly with probability exponentially
small in k.

In this talk, I am going to present some of recent progress on direct sum
and direct product theorems in the model of communication complexity and
two-prover one-round  games with information-theoretic approach. The talk
is based on parts of my doctoral work.

Date: Wednesday, February 12, 2014.
Time: 16:00
Location: Time Room (294)

-Gus
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.uwaterloo.ca/pipermail/quantum-info/attachments/20140210/43d43390/attachment.html>