Uniform direct product theorems: simplified, optimized, and derandomized

No abstract is available for this paper.

• Publication year

  2008

• Venue

  SIAM journal on computing (Print)

• Publication date

  2008-05-17

• Fields of study

  Mathematics, Computer Science

• Identifiers
  DOI 10.1145/1374376.1374460
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• New direct-product testers and 2-query PCPs

  2009cited by this paper
• Approximate List-Decoding of Direct Product Codes and Uniform Hardness Amplification

  2009influential reference
• Verifying and decoding in constant depth

  2007cited by this paper
• Chernoff-Type Direct Product Theorems

  2007cited by this paper
• Making hard problems harder

  2006cited by this paper
• On uniform amplification of hardness in NP

  2005influential reference
• Assignment testers: towards a combinatorial proof of the PCP-theorem

  2004cited by this paper
• Hardness as randomness: a survey of universal derandomization

  2003cited by this paper
• Pseudorandomness and Average-Case Complexity Via Uniform Reductions

  2002cited by this paper
• Pseudorandom generators without the XOR lemma

  1999cited by this paper
• Randomness-optimal oblivious sampling

  1997cited by this paper
• A Combinatorial Consistency Lemma with Application to Proving the PCP Theorem

  1997cited by this paper
• Improved Low-Degree Testing and its Applications

  1997influential reference
• A sub-constant error-probability low-degree test, and a sub-constant error-probability PCP characterization of NP

  1997cited by this paper
• P = BPP if E requires exponential circuits: derandomizing the XOR lemma

  1997influential reference
• On Yao's XOR-Lemma

  1995cited by this paper
• Hard-core distributions for somewhat hard problems

  1995cited by this paper
• Probability Inequalities for Sums of Bounded Random Variables

  1994cited by this paper
• Randomness in interactive proofs

  1990cited by this paper
• A hard-core predicate for all one-way functions

  1989cited by this paper
• One-way functions and pseudorandom generators

  1985cited by this paper
• Theory and Applications of Trapdoor Functions (Extended Abstract)

  1982cited by this paper
• Theory and application of trapdoor functions

  1982influential reference

• Towards Free Lunch Derandomization from Necessary Assumptions (and OWFs)

  2025cites this paper
• Error-Correction of Matrix Multiplication Algorithms

  2025cites this paper
• Hypercontractivity on HDX II: Symmetrization and 𝑞-Norms

  2025cites this paper
• NP-hardness of the Minimum Circuit Size Problem from Well-Studied Assumptions

  2025cites this paper
• Opening Up the Distinguisher: A Hardness to Randomness Approach for BPL=L That Uses Properties of BPL

  2024cites this paper
• A Strong Direct Sum Theorem for Distributional Query Complexity

  2024cites this paper
• Agreement Theorems for High Dimensional Expanders in the Low Acceptance Regime: The Role of Covers

  2024cites this paper
• Chernoff Bounds and Reverse Hypercontractivity on HDX

  2024cites this paper
• Planted Clique Conjectures Are Equivalent

  2024influential citation
• Approximate Locally Decodable Codes with Constant Query Complexity and Nearly Optimal Rate

  2024cites this paper
• Direct sum theorems beyond query complexity

  2024cites this paper
• Query complexity lower bounds for local list-decoding and hard-core predicates (even for small rate and huge lists)

  2024cites this paper
• Hardness vs. Randomness, Revised: Uniform, Non-Black-Box, and Instance-wise

  2024cites this paper
• Hypercontractivity on HDX II: Symmetrization and q-Norms

  2024cites this paper
• On Approximability of Satisfiable k-CSPs: IV

  2023cites this paper
• Swap Cosystolic Expansion

  2023cites this paper
• Agreement theorems for high dimensional expanders in the small soundness regime: the role of covers

  2023cites this paper
• Hardness Self-Amplification: Simplified, Optimized, and Unified

  2023influential citation
• A High Dimensional Goldreich-Levin Theorem

  2023cites this paper
• Hardness Self-Amplification from Feasible Hard-Core Sets

  2022cites this paper
• Hardness vs Randomness, Revised: Uniform, Non-Black-Box, and Instance-Wise

  2022cites this paper
• Strong Average-Case Circuit Lower Bounds from Non-trivial Derandomization

  2022cites this paper
• Unstructured Hardness to Average-Case Randomness

  2022influential citation
• Excluding PH Pessiland

  2022cites this paper
• Spoofing Generalization: When Can't You Trust Proprietary Models?

  2021cites this paper
• Erasures versus errors in local decoding and property testing

  2021influential citation
• List-Decoding with Double Samplers

  2021cites this paper
• Strong average-case lower bounds from non-trivial derandomization

  2020cites this paper
• Theory of Cryptography: 18th International Conference, TCC 2020, Durham, NC, USA, November 16–19, 2020, Proceedings, Part III

  2020influential citation
• Quantum learning algorithms imply circuit lower bounds

  2020cites this paper
• An 8.4 Gbps real-time quantum random number generator based on quantum phase fluctuation

  2020cites this paper
• Characterizing Average-Case Complexity of PH by Worst-Case Meta-Complexity

  2020cites this paper
• Nearly Optimal Average-Case Complexity of Counting Bicliques Under SETH

  2020cites this paper
• Super-Linear Time-Memory Trade-Offs for Symmetric Encryption

  2020cites this paper
• Computational Complexity and Property Testing: On the Interplay Between Randomness and Computation

  2020cites this paper
• Relations and equivalences between circuit lower bounds and karp-lipton theorems

  2019cites this paper
• On the impact of cryptography on complexity theory

  2019cites this paper
• Non-deterministic Quasi-Polynomial Time is Average-Case Hard for ACC Circuits

  2019cites this paper
• Erasures vs. Errors in Local Decoding and Property Testing

  2019cites this paper
• Approximation and Hardness: Beyond P and NP

  2019cites this paper
• Testing tensor products

  2019cites this paper
• XOR Codes and Sparse Learning Parity with Noise

  2019cites this paper
• List Decoding with Double Samplers

  2018cites this paper
• Indistinguishability by Adaptive Procedures with Advice, and Lower Bounds on Hardness Amplification Proofs

  2018cites this paper
• From Local to Robust Testing via Agreement Testing

  2018cites this paper
• Worst-case to Average-case reductions for subclasses of P

  2017cites this paper
• Learning Algorithms from Natural Proofs

  2016cites this paper
• Algorithms from Natural Lower Bounds

  2016cites this paper
• Cryptographic Assumptions: A Position Paper

  2016cites this paper
• Direct Sum Testing

  2015cites this paper
• Advice Lower Bounds for the Dense Model Theorem

  2015cites this paper
• A note on the relation between XOR and Selective XOR Lemmas

  2014cites this paper
• It'll Probably Work Out: Improved List-Decoding Through Random Operations

  2014cites this paper
• On Uniform Reductions between Direct Product and XOR Lemmas

  2014cites this paper
• Tree-Structured Composition of Homomorphic Encryption: How to Weaken Underlying Assumptions

  2014cites this paper
• A theory of locally decodable codes

  2013cites this paper
• Nondeterministic Direct Product Reductions and the Success Probability of SAT Solvers

  2013cites this paper
• The Computational Complexity of Randomness

  2013cites this paper
• Clustering in the Boolean Hypercube in a List Decoding Regime

  2013cites this paper
• Resource-based corruptions and the combinatorics of hidden diversity

  2013cites this paper
• The complexity of joint computation

  2012cites this paper
• Lower Bounds on the Query Complexity of Non-uniform and Adaptive Reductions Showing Hardness Amplification

  2011cites this paper
• The Complexity of Entangled Games

  2011cites this paper
• Query Complexity in Errorless Hardness Amplification

  2011cites this paper
• Some Recent Results on Local Testing of Sparse Linear Codes

  2010cites this paper
• A PCP Characterization of AM

  2010cites this paper
• Almost Optimal Bounds for Direct Product Threshold Theorem

  2010cites this paper
• Derandomized Parallel Repetition Theorems for Free Games

  2010cites this paper
• PCPs for Arthur-Merlin Games and Communication Protocols

  2010cites this paper
• General Hardness Amplification of Predicates and Puzzles

  2010cites this paper
• A Note on Amplifying the Error-Tolerance of Locally Decodable Codes

  2010cites this paper
• Constructive Proofs of Concentration Bounds

  2010cites this paper
• Local list-decoding and testing of random linear codes from high error

  2010cites this paper
• Improved direct product theorems for randomized query complexity

  2010cites this paper
• Derandomized Parallel Repetition of Structured PCPs

  2010cites this paper
• Local List Decoding with a Constant Number of Queries

  2010cites this paper
• Parallel repetition of entangled games

  2010influential citation
• Complexity in Errorless Hardness Amplification

  2010cites this paper
• Derandomized Parallel Repetition via Structured PCPs

  2010cites this paper
• Computational Indistinguishability Amplification

  2010cites this paper
• Explorer A PCP Characterization of AM

  2010cites this paper
• Photonics for THz quantum cascade lasers

  2010cites this paper
• New direct-product testers and 2-query PCPs

  2009cites this paper
• Security Amplification for InteractiveCryptographic Primitives

  2009cites this paper
• The uniform hardcore lemma via approximate Bregman projections

  2009cites this paper
• Local Decoding in Constant Depth

  2009cites this paper
• Extractors Using Hardness Amplification

  2009cites this paper
• Proofs of Retrievability via Hardness Amplification

  2009cites this paper
• 1 Direct Product Theorems

  2009cites this paper
• A strong direct product theorem for disjointness

  2009cites this paper
• Delegating computation reliably: paradigms and constructions

  2009cites this paper
• On the complexity of differentially private data release: efficient algorithms and hardness results

  2009cites this paper
• Locally Testing Direct Products in the High Error Range

  2008cites this paper
• Locally Testing Direct Product in the Low Error Range

  2008cites this paper
• Hardness Amplification within NP against Deterministic Algorithms

  2008cites this paper
• The Complexity of Local List Decoding

  2008influential citation
• When and How Can Data be Efficiently Released with Privacy ?

  2008cites this paper
• Deterministic Hardness Amplification via Local GMD Decoding

  2007cites this paper
• Chernoff-Type Direct Product Theorems

  2007cites this paper
• On the Complexity of Hardness Amplification

  2005cites this paper