PIRSA:14020142

Applications of Information Theory in Direct Sum and Direct Product Problems

APA

(2014). Applications of Information Theory in Direct Sum and Direct Product Problems. Perimeter Institute for Theoretical Physics. https://pirsa.org/14020142

MLA

Applications of Information Theory in Direct Sum and Direct Product Problems. Perimeter Institute for Theoretical Physics, Feb. 12, 2014, https://pirsa.org/14020142

BibTex

          @misc{ scivideos_PIRSA:14020142,
            doi = {10.48660/14020142},
            url = {https://pirsa.org/14020142},
            author = {},
            keywords = {Quantum Information},
            language = {en},
            title = {Applications of Information Theory in Direct Sum and Direct Product Problems},
            publisher = {Perimeter Institute for Theoretical Physics},
            year = {2014},
            month = {feb},
            note = {PIRSA:14020142 see, \url{https://scivideos.org/pirsa/14020142}}
          }
          
Talk numberPIRSA:14020142
Source RepositoryPIRSA

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.