Fetching the paper…
Reading the bibliography…
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.
Probabilistic computations: Toward a unified measure of complexity (extended abstract)
Andrew Chi-Chih Yao · 1977
Earlier work this paper cites.
Crew prams and decision trees
Noam Nisan · 1989
Earlier work this paper cites.
Computing with noisy information
Uriel Feige, Prabhakar Raghavan, David Peleg, and Eli Upfal · 1990
Earlier work this paper cites.
A direct product theorem
Russell Impagliazzo, Ran Raz, and Avi Wigderson · 1994
Earlier work this paper cites.
Products and help bits in decision trees
Noam Nisan, Steven Rudich, and Michael E. Saks · 1994
Earlier work this paper cites.
On Yao’s XOR-lemma
Oded Goldreich, Noam Nisan, and Avi Wigderson · 1995
Earlier work this paper cites.
Hard-core distributions for somewhat hard problems
Russell Impagliazzo · 1995
Earlier work this paper cites.
Towards proving strong direct product theorems
Ronen Shaltiel · 2001
Earlier work this paper cites.
Complexity measures and decision tree complexity: a survey
Harry Buhrman and Ronald de Wolf · 2002
Earlier work this paper cites.
Indistinguishability of random systems
Ueli M. Maurer · 2002
Earlier work this paper cites.
Quantum and classical strong direct product theorems and optimal time-space tradeoffs
Hartmut Klauck, Robert Špalek, and Ronald de Wolf · 2004
Cited alongside, same era.
Robust polynomials and quantum algorithms
Harry Buhrman, Ilan Newman, Hein Röhrig, and Ronald de Wolf · 2005
Cited alongside, same era.
Key agreement from weak bit agreement
Thomas Holenstein · 2005
Cited alongside, same era.
A new quantum lower bound method, with applications to direct product theorems and time-space tradeoffs
Andris Ambainis, Robert Spalek, and Ronald de Wolf · 2006
Cited alongside, same era.
Indistinguishability amplification
Ueli M. Maurer, Krzysztof Pietrzak, and Renato Renner · 2007
Cited alongside, same era.
Norms, XOR lemmas, and lower bounds for polynomials and protocols
Emanuele Viola and Avi Wigderson · 2007
Cited alongside, same era.
A probabilistic inequality with applications to threshold direct-product theorems
Falk Unger · 2009
Later among the works it cites.
Constructive proofs of concentration bounds
Russell Impagliazzo and Valentine Kabanets · 2010
Closest in time.
Optimal direct sum results for deterministic and randomized decision tree complexity
Rahul Jain, Hartmut Klauck, and Miklos Santha · 2010
Closest in time.
A strong direct product theorem for disjointness
Hartmut Klauck · 2010
Closest in time.
Symmetry-assisted adversaries for quantum state generation
Andris Ambainis, Loïck Magnin, Martin Roetteler, and Jérémie Roland · 2011
Closest in time.
General hardness amplification of predicates and puzzles - (extended abstract)
Thomas Holenstein and Grant Schoenebeck · 2011
Closest in time.
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
Uniform direct product theorems: Simplified, optimized, and derandomized
Russell Impagliazzo, Ragesh Jaiswal, Valentine Kabanets, and Avi Wigderson · 2008
Cited alongside, same era.
A direct product theorem for discrepancy
Troy Lee, Adi Shraibman, and Robert Špalek · 2008
Cited alongside, same era.
The multiplicative quantum adversary
Robert Špalek · 2008
Cited alongside, same era.
Concentration of Measure for the Analysis of Randomized Algorithms
Devdatt P. Dubhashi and Alessandro Panconesi · 2009
Cited alongside, same era.
New strong direct product results in communication complexity
Rahul Jain · 2011
Closest in time.
Strong direct product theorems for quantum communication and query complexity
Alexander A. Sherstov · 2011
Closest in time.
A direct product theorem for bounded-round public-coin randomized communication complexity
Rahul Jain, Attila Pereszlényi, and Penghui Yao · 2012
Closest in time.
A strong direct product theorem for quantum query complexity
Troy Lee and Jérémie Roland · 2012
Closest in time.