Bounds on 2-query locally testable codes with affine tests

DOI10.1016/J.IPL.2016.03.008MaRDI QIDQ280942zbMATH OpenOpenAlexFDO

Authors 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) Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science) (68P30) Bounds on codes (94B65) Other types of codes (94B60)

Recommendations

• Bounds on locally testable codes with unique tests
• Bounds on \(2\)-query codeword testing
• Limitations on Testable Affine-Invariant Codes in the High-Rate Regime
• Lower bounds for constant query affine-invariant LCCs and LTCs
• Locally Testable Codes Require Redundant Testers

Cites work

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

Cited in

(6)

• Towards lower bounds on locally testable codes via density arguments
• On 2-Query Codeword Testing with Near-Perfect Completeness
• Limitations on Testable Affine-Invariant Codes in the High-Rate Regime
• Bounds on \(2\)-query codeword testing
• Limits on the Rate of Locally Testable Affine-Invariant Codes
• Bounds on locally testable codes with unique tests

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q280942)