Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #1 to TR10-080 | 9th May 2014 14:54

Improved Direct Product Theorems for Randomized Query Complexity

RSS-Feed




Revision #1
Authors: Andrew Drucker
Accepted on: 9th May 2014 14:54
Downloads: 355
Keywords: 


Abstract:

The direct product problem is a fundamental question in complexity theory which seeks to understand how the difficulty of computing a function on each of $k$ independent inputs scales with $k$.
We prove the following direct product theorem (DPT) for query complexity: if every $T$-query algorithm
has success probability at most $1 - \eps$ in computing the Boolean function $f$ on input distribution $\mu$, then for $\alpha \leq 1$, every $\alpha \eps Tk$-query algorithm has success probability at most $(2^{\alpha \eps}(1-\eps))^k$ in computing the $k$-fold direct product $f^{\otimes k}$ correctly on $k$ independent inputs from $\mu$. In light of examples due to Shaltiel, this statement gives an essentially optimal tradeoff between the query bound and the error probability. As a corollary, we show that for an absolute constant $\alpha > 0$, the worst-case success probability of any $\alpha R_2(f) k$-query randomized algorithm for $f^{\otimes k}$ falls exponentially with $k$. The best previous statement of this type, due to Klauck, Spalek, and de Wolf, required a query bound of $O(bs(f) k)$.

The proof involves defining and analyzing a collection of martingales associated with an algorithm attempting to solve $f^{\otimes k}$. Our method is quite general and yields a new XOR lemma and threshold DPT for the query model, as well as DPTs for the query complexity of learning tasks, search problems, and tasks involving interaction with dyamic entities. We also give a version of our DPT in which decision tree size is the resource of interest.



Changes to previous version:

Updated to essentially match journal version (which includes minor fixes, comparison with previous interactive DPTs, improved writing).


Paper:

TR10-080 | 5th May 2010 00:11

Improved Direct Product Theorems for Randomized Query Complexity





TR10-080
Authors: Andrew Drucker
Publication: 5th May 2010 01:55
Downloads: 1506
Keywords: 


Abstract:

The direct product problem is a fundamental question in complexity theory which seeks to understand how the difficulty of computing a function on each of $k$ independent inputs scales with $k$.
We prove the following direct product theorem (DPT) for query complexity: if every $T$-query algorithm
has success probability at most $1 - \eps$ in computing the Boolean function $f$ on input distribution $\mu$, then for $\alpha \leq 1$, every $\alpha \eps Tk$-query algorithm has success probability at most $(2^{\alpha \eps}(1-\eps))^k$ in computing the $k$-fold direct product $f^{\otimes k}$ correctly on $k$ independent inputs from $\mu$. In light of examples due to Shaltiel, this statement gives an essentially optimal tradeoff between the query bound and the error probability. As a corollary, we show that for an absolute constant $\alpha > 0$, the worst-case success probability of any $\alpha R_2(f) k$-query randomized algorithm for $f^{\otimes k}$ falls exponentially with $k$. The best previous statement of this type, due to Klauck, Spalek, and de Wolf, required a query bound of $O(bs(f) k)$.

The proof involves defining and analyzing a collection of martingales associated with an algorithm attempting to solve $f^{\otimes k}$. Our method is quite general and yields a new XOR lemma and threshold DPT for the query model, as well as DPTs for the query complexity of learning tasks, search problems, and tasks involving interaction with dyamic entities. We also give a version of our DPT in which decision tree size is the resource of interest.



ISSN 1433-8092 | Imprint