Friday, November 2, 2007
3:30 pm, MC 5158

Tutte Seminar Series
Combinatorics & Optimization
Fall 2007

Ashwin Nayak
University of Waterloo

The Direct-Product Property, Subdistribution Bounds, and Applications

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).