Approximate list-decoding of direct product codes and uniform hardness amplification
DOI10.1137/070683994zbMATH Open1200.68142OpenAlexW2013948267MaRDI QIDQ3558014FDOQ3558014
Valentine Kabanets, Ragesh Jaiswal, Russell Impagliazzo
Publication date: 29 April 2010
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/070683994
Recommendations
- Uniform direct product theorems: simplified, optimized, and derandomized
- Hardness amplification within NP against deterministic algorithms
- Hardness amplification via space-efficient direct products
- Hardness Amplification Via Space-Efficient Direct Products
- New direct-product testers and 2-query PCPs
error-correcting codesdirect product theoremsapproximately list-decodable codesuniform hardness amplificationYao's XOR Lemma
Formal languages and automata (68Q45) Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science) (68P30) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)
Cited In (10)
- Lower Bounds on the Query Complexity of Non-uniform and Adaptive Reductions Showing Hardness Amplification
- Title not available (Why is that?)
- Hardness Amplification Via Space-Efficient Direct Products
- On Yao’s XOR-Lemma
- Lower bounds on the query complexity of non-uniform and adaptive reductions showing hardness amplification
- Hardness amplification within NP against deterministic algorithms
- Chernoff-type direct product theorems
- Advice lower bounds for the dense model theorem
- A high dimensional Goldreich-Levin theorem
- Hardness self-amplification: simplified, optimized, and unified
This page was built for publication: Approximate list-decoding of direct product codes and uniform hardness amplification
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3558014)
