Friday, November 2, 2007 3:30 pm
-
4:30 pm
EDT (GMT -04:00)
The Direct-Product Property, Subdistribution Bounds, and Applications
Speaker: | Ashwin Nayak |
---|---|
Affiliation: | University of Waterloo |
Room: | Mathematics & Computer Building (MC) 5158 |
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).