Bounds on 2-query locally testable codes with affine tests

DOI10.1016/j.ipl.2016.03.008zbMath1357.68051OpenAlexW2303247699MaRDI QIDQ280942

Gillat Kol, Ran Raz

Publication date: 10 May 2016

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ipl.2016.03.008

zbMATH Keywords

computational complexitytheory of computationlocally testable codesunique games conjecture

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Bounds on codes (94B65) Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science) (68P30) Other types of codes (94B60)

Related Items (1)

Towards lower bounds on locally testable codes via density arguments

Cites Work

• Unnamed Item
• Non-deterministic exponential time has two-prover interactive protocols
• Noise stability of functions with low influences: invariance and optimality
• On the hardness of approximating Multicut and Sparsest-Cut
• Vertex cover might be hard to approximate to within \(2 - \varepsilon \)
• Bounds on locally testable codes with unique tests
• Proof verification and the hardness of approximation problems
• Locally testable codes and PCPs of almost-linear length
• Conditional Hardness for Approximate Coloring
• On the power of unique 2-prover 1-round games
• Probabilistic checking of proofs
• Interactive proofs and the hardness of approximating cliques
• Optimal Inapproximability Results for MAX‐CUT and Other 2‐Variable CSPs?
• On 2-Query Codeword Testing with Near-Perfect Completeness
• Some 3CNF Properties Are Hard to Test
• Robust PCPs of Proximity, Shorter PCPs, and Applications to Coding
• Approximation, Randomization, and Combinatorial Optimization.. Algorithms and Techniques

This page was built for publication: Bounds on 2-query locally testable codes with affine tests