PIRSA:14020142

Applications of Information Theory in Direct Sum and Direct Product Problems

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

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

          @misc{ pirsa_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},
            year = {2014},
            month = {feb},
            note = {PIRSA:14020142 see, \url{https://pirsa.org}}
          }
DOI 10.48660/14020142
Collection
Talk Type Scientific Series
Subject

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.