Combinatorial Construction of Locally Testable Codes

DOI10.1137/080729967zbMath1202.68235OpenAlexW2057157452MaRDI QIDQ3558012

Or Meir

Publication date: 29 April 2010

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://semanticscholar.org/paper/29189cbe958616ae20efc09d9fc9f4f27095e548

zbMATH Keywords

probabilistically checkable proofslocally testable codes (LTCs)PCPs of proximity

Mathematics Subject Classification ID

Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science) (68P30) Other types of codes (94B60)

Related Items (19)

Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Local List Recovery of High-Rate Tensor Codes and Applications ⋮ The tensor product of two good codes is not necessarily robustly testable ⋮ On the rectangle method in proofs of robustness of tensor products ⋮ Tensor Products of Weakly Smooth Codes Are Robust ⋮ Relaxed Locally Correctable Codes ⋮ Composition of semi-LTCs by two-wise tensor products ⋮ Towards lower bounds on locally testable codes via density arguments ⋮ Limitation on the Rate of Families of Locally Testable Codes ⋮ Short Locally Testable Codes and Proofs: A Survey in Two Parts ⋮ Smooth and strong PCPs ⋮ Dense Locally Testable Codes Cannot Have Constant Rate and Distance ⋮ Short Locally Testable Codes and Proofs ⋮ A combinatorial characterization of smooth LTCs and applications ⋮ On the Power of Relaxed Local Decoding Algorithms ⋮ Unnamed Item ⋮ A combination of testability and decodability by tensor products

This page was built for publication: Combinatorial Construction of Locally Testable Codes