Abstract
The “direct product problem” is a fundamental question in complexity theory which seeks to understand how the difficulty in 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 - \varepsilon}\) in computing the Boolean function f on input distribution μ, then for α ≤ 1, every \({\alpha \varepsilon Tk}\)-query algorithm has success probability at most \({(2^{\alpha \varepsilon}(1-\varepsilon))^k}\) in computing the k-fold direct product \({f^{\otimes k}}\) correctly on k independent inputs from μ. In light of examples due to Shaltiel, this statement gives an essentially optimal trade-off between the query bound and the error probability. Using this DPT, we show that for an absolute constant α > 0, the worst-case success probability of any α 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, Špalek, and de Wolf, required a query bound of O(bs(f) k).
Our proof technique 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 dynamic entities. We also give a version of our DPT in which decision tree size is the resource of interest.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Andris Ambainis, Loïck Magnin, Martin Roetteler, Jérémie Roland (2011). Symmetry-Assisted Adversaries for Quantum State Generation. In 26th IEEE Conference on Computational Complexity, 167–177.
Andris Ambainis, Robert Špalek, de Ronald Wolf (2009) A New Quantum Lower Bound Method, with Applications to Direct Product Theorems and Time-Space Tradeoffs. Algorithmica 55(3): 422–461 Earlier version in STOC 2006.
Harry Buhrman, Ilan Newman, Hein Röhrig, de Ronald Wolf (2007) Robust Polynomials and Quantum Algorithms. Theory Comput. Syst. 40(4): 379–395 Earlier version in STACS 2005.
Harry Buhrman, de Ronald Wolf (2002) Complexity Measures and Decision Tree Complexity: a Survey. Theor. Comput. Sci. 288(1): 21–43
Devdatt P. Dubhashi & Alessandro Panconesi (2009). Concentration of Measure for the Analysis of Randomized Algorithms. Cambridge University Press, 1st edition.
Uriel Feige, Prabhakar Raghavan, David Peleg, Eli Upfal (1994) Computing with Noisy Information. SIAM J. Comput. 23(5): 1001–1018 Earlier version in STOC 1990.
Oded Goldreich, Noam Nisan & Avi Wigderson (1995). On Yao’s XOR-Lemma. Electronic Colloquium on Computational Complexity (ECCC) TR95-050.
Thomas Holenstein (2005). Key Agreement from Weak Bit Agreement. In 37th ACM STOC, 664–673.
Thomas Holenstein & Grant Schoenebeck (2011). General Hardness Amplification of Predicates and Puzzles - (Extended Abstract). In TCC, 19–36.
Russell Impagliazzo (1995). Hard-Core Distributions for Somewhat Hard Problems. In 36th IEEE FOCS, 538–545.
Russell Impagliazzo, Ragesh Jaiswal, Valentine Kabanets, Avi Wigderson (2010) Uniform Direct Product Theorems: Simplified, Optimized, and Derandomized. SIAM J. Comput. 39(4): 1637–1665 Earlier version in STOC 2008.
Russell Impagliazzo & Valentine Kabanets (2010). Constructive Proofs of Concentration Bounds. In 14th APPROX-RANDOM, 617–631.
Russell Impagliazzo, Ran Raz & Avi Wigderson (1994). A Direct Product Theorem. In 9th IEEE Structure in Complexity Theory Conference, 88–96.
Russell Impagliazzo & Avi Wigderson (1997). P = BPP if E Requires Exponential Circuits: Derandomizing the XOR Lemma. In 29th ACM STOC, 220–229.
Rahul Jain (2011). New strong direct product results in communication complexity. Electronic Colloquium on Computational Complexity (ECCC) TR11-024.
Rahul Jain, Hartmut Klauck, Miklos Santha (2010) Optimal Direct Sum Results for Deterministic and Randomized Decision Tree Complexity. Inf. Process. Lett. 110: 893–897
Rahul Jain, Attila Pereszlényi & Penghui Yao (2012). A direct product theorem for bounded-round public-coin randomized communication complexity. CoRR abs/1201.1666.
Hartmut Klauck (2010). A Strong Direct Product Theorem for Disjointness. In 42nd ACM STOC, 77–86.
Hartmut Klauck, Robert Špalek, de Ronald Wolf (2007) Quantum and Classical Strong Direct Product Theorems and Optimal Time-Space Tradeoffs. SIAM J. Comput. 36(5): 1472–1493 Earlier version in FOCS 2004.
Troy Lee & Jérémie Roland (2011). A Strong Direct Product Theorem for Quantum Query Complexity. CoRR abs/1104.4468. To appear in CCC 2012.
Troy Lee, Adi Shraibman & Robert Špalek (2008). A Direct Product Theorem for Discrepancy. In 23rd IEEE Conference on Computational Complexity, 71–80.
Ueli M. Maurer (2002). Indistinguishability of Random Systems. In 21st EUROCRYPT, 110–132.
Ueli M. Maurer, Krzysztof Pietrzak & Renato Renner (2007). Indistinguishability Amplification. In 27th CRYPTO, 130–149.
Noam Nisan (1991) CREW PRAMs and Decision Trees. SIAM J. Comput. 20(6): 999–1007 Earlier version in STOC 1989.
Noam Nisan, Steven Rudich, Michael E. Saks (1999) Products and Help Bits in Decision Trees. SIAM J. Comput. 28(3): 1035–1050 Earlier version in FOCS 1994.
Ronen Shaltiel (2003) Towards Proving Strong Direct Product Theorems. Computational Complexity 12(1-2): 1–22 Earlier version in CCC 2001.
Alexander A. Sherstov (2011). Strong direct product theorems for quantum communication and query complexity. In 43rd ACM STOC, 41–50.
Robert Špalek (2008). The Multiplicative Quantum Adversary. In 23rd IEEE Conference on Computational Complexity, 237–248.
Falk Unger (2009). A Probabilistic Inequality with Applications to Threshold Direct-Product Theorems. In 50th IEEE FOCS, 221–229.
Emanuele Viola, Avi Wigderson (2008) Norms, XOR Lemmas, and Lower Bounds for Polynomials and Protocols. Theory of Computing 4(1): 137–168 Earlier version in CCC 2007.
Andrew Chi-Chih Yao (1977). Probabilistic Computations: Toward a Unified Measure of Complexity (Extended Abstract). In 18th IEEE FOCS, 222–227.
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Drucker, A. Improved direct product theorems for randomized query complexity. comput. complex. 21, 197–244 (2012). https://doi.org/10.1007/s00037-012-0043-7
Received:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00037-012-0043-7