Penghui Yao (Centre for Quantum Technologies, 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(kc) 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.