The Direct-Product Property, Subdistribution Bounds, and Applications
|Affiliation:||University of Waterloo|
|Room:||Mathematics & Computer Building (MC) 5158|
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).
200 University Avenue West
Waterloo, ON N2L 3G1