Approximate List-Decoding of Direct Product Codes and Uniform Hardness Amplification

DOI10.1137/070683994zbMath1200.68142OpenAlexW2013948267MaRDI QIDQ3558014

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

zbMATH Keywords

error-correcting codesdirect product theoremsapproximately list-decodable codesuniform hardness amplificationYao's XOR Lemma

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Formal languages and automata (68Q45) 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)

Related Items (7)

Hardness amplification within NP against deterministic algorithms ⋮ Unnamed Item ⋮ 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 ⋮ Advice Lower Bounds for the Dense Model Theorem ⋮ Chernoff-type direct product theorems

This page was built for publication: Approximate List-Decoding of Direct Product Codes and Uniform Hardness Amplification