|
Friday, November 2, 2007 |
|
|
|
|
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.
|