Tutte seminar - Ashwin Nayak

The Direct-Product Property, Subdistribution Bounds, and Applications

Abstract:

A basic question in complexity theory is whether the computational resources required for solving k independent instances of the same problem scale as k times the resources required for one instance. In this talk, we revisit a few instances where this kind of "direct product'' property occurs in quantum communication. We then define a new notion of complexity for boolean functions, a "subdistribution bound'', and explain how this enables us to prove the direct product property in some instances. This way we recover and generalize, in a unified manner, several recent results on the direct product question.

Joint work with Rahul Jain (U. Waterloo) and Hartmut Klauck (Goethe-U., Frankfurt).