Hardness Amplification Via Space-Efficient Direct Products

DOI10.1007/11682462_52MaRDI QIDQ3525791zbMATH OpenOpenAlexFDO

Authors Valentine Kabanets, Venkatesan Guruswami

Publication date 18 September 2008

Published in LATIN 2006: Theoretical Informatics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/11682462_52

zbMATH Keywords

direct productserror-correcting codesexpandershardness amplification

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) 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)

• Hardness amplification via space-efficient direct products
• Approximate list-decoding of direct product codes and uniform hardness amplification
• Uniform direct product theorems: simplified, optimized, and derandomized
• Hardness amplification within NP against deterministic algorithms
• Almost-catalytic computation

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 Q3525791)