Bounds on 2-query locally testable codes with affine tests

DOI10.1016/J.IPL.2016.03.008zbMATH Open1357.68051OpenAlexW2303247699MaRDI QIDQ280942FDOQ280942

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

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

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)

Cites Work

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

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)