Showing cs.CCShow all
2 papers · 1 filter
cs.CC2010
Strong direct product theorems for quantum communication and query complexity
Alexander A. Sherstov
A strong direct product theorem (SDPT) states that solving n instances of a problem requires Omega(n) times the resources for a single instance, even to achieve success probability…
cs.CC2009
The Pattern Matrix Method (Journal Version)
Alexander A. Sherstov
We develop a novel and powerful technique for communication lower bounds, the pattern matrix method. Specifically, fix an arbitrary function f:{0,1}^n->{0,1} and let A_f be the mat…