Hardness amplification via space-efficient direct products

DOI10.1007/S00037-008-0253-1MaRDI QIDQ2269003zbMATH OpenOpenAlexFDO

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

zbMATH Keywords

derandomized Direct Product Lemmadeterministic space-bounded algorithms

Mathematics Subject Classification ID

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)

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

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
• Approximate list-decoding of direct product codes and uniform hardness amplification
• Lower bounds on the query complexity of non-uniform and adaptive reductions showing 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)