Le contenu de cette page n’est pas disponible en français. Veuillez nous en excuser.
 

Applications of Information Theory in Direct Sum and Direct Product Problems



Playing this video requires the latest flash player from Adobe.

Download link (right click and 'save-as') for playing in VLC or other f4v compatible player.


Recording Details

Speaker(s): 
Scientific Areas: 
PIRSA Number: 
14020142

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.