Uniform Direct Product Theorems: Simplified, Optimized, and Derandomized

DOI10.1137/080734030zbMath1206.68131OpenAlexW1989019709MaRDI QIDQ3586194

Avi Wigderson, Russell Impagliazzo, Valentine Kabanets, Ragesh Jaiswal

Publication date: 6 September 2010

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/080734030

zbMATH Keywords

error-correcting codedirect product theoremYao's XOR Lemmadirect product codelist-decoding algorithms

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science) (68P30) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Randomized algorithms (68W20)

Related Items (18)

Strong Average-Case Circuit Lower Bounds from Nontrivial Derandomization ⋮ Worst-Case to Average-Case Reductions for Subclasses of P ⋮ Erasures versus errors in local decoding and property testing ⋮ Query complexity in errorless hardness amplification ⋮ Unnamed Item ⋮ A note on the relation between XOR and selective XOR lemmas ⋮ A PCP Characterization of AM ⋮ Improved direct product theorems for randomized query complexity ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Cryptographic Assumptions: A Position Paper ⋮ Lower bounds on the query complexity of non-uniform and adaptive reductions showing hardness amplification ⋮ Lower Bounds on the Query Complexity of Non-uniform and Adaptive Reductions Showing Hardness Amplification ⋮ On Yao’s XOR-Lemma ⋮ Relations and equivalences between circuit lower bounds and karp-lipton theorems ⋮ Advice Lower Bounds for the Dense Model Theorem ⋮ List-Decoding with Double Samplers ⋮ Direct Sum Testing

This page was built for publication: Uniform Direct Product Theorems: Simplified, Optimized, and Derandomized