Hardness amplification via space-efficient direct products
DOI10.1007/S00037-008-0253-1zbMATH Open1188.68152OpenAlexW2035701586MaRDI QIDQ2269003FDOQ2269003
Authors: Venkatesan Guruswami, Valentine Kabanets 
Publication date: 15 March 2010
Published in: Computational Complexity (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s00037-008-0253-1
Recommendations
- Hardness Amplification Via Space-Efficient Direct Products
- Uniform direct product theorems: simplified, optimized, and derandomized
- Hardness amplification within NP against deterministic algorithms
- Approximate list-decoding of direct product codes and uniform hardness amplification
- New direct-product testers and 2-query PCPs
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) Linear codes (general theory) (94B05) Decoding (94B35)
Cited In (5)
- Lower Bounds on the Query Complexity of Non-uniform and Adaptive Reductions Showing Hardness Amplification
- Hardness Amplification Via Space-Efficient Direct Products
- Uniform direct product theorems: simplified, optimized, and derandomized
- Lower bounds on the query complexity of non-uniform and adaptive reductions showing hardness amplification
- Approximate list-decoding of direct product codes and uniform hardness amplification
This page was built for publication: Hardness amplification via space-efficient direct products
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2269003)
