[quantum-info] IQC Seminar Thursday Feb. 13 noon
Matthew Fries
mfries at uwaterloo.ca
Thu Feb 13 07:43:04 EST 2014
Seminar
Institute for Quantum Computing
Thursday, 13 February 2014 at 12:00PM
QNC 0101
Applications of Information Theory in Direct Sum and Direct Product Problems
Penghui Yao
National University of Singapore
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.
More information about the quantum-info
mailing list