NDLI: Towards lower bounds on locally testable codes via density arguments

Please wait, while we are loading the content...

Towards lower bounds on locally testable codes via density arguments

Content Provider	Springer Nature Link
Author	Viderman, Michael Ben Sasson, Eli
Copyright Year	2012
Abstract	The main open problem in the area of locally testable codes (LTCs) is whether there exists an asymptotically good family of LTCs, and to resolve this question, it suffices to consider the case of query complexity 3. We argue that to refute the existence of such an asymptotically good family, it is sufficient to prove that the number of dual codewords of weight at most 3 is super-linear in the blocklength of the code and they are distributed “naturally”.The main technical contribution of this paper is an improvement of the combinatorial lemma of Goldreich et al. (Comput Complex 15(3):263–296, 2006) which bounds the rate of 2-query locally decodable codes (LDCs) and is used in state-of-the-art rate bounds for linear LDCs. The lemma of Goldreich et al. bounds the rate of 2-query LDCs of blocklength n in terms of the corruption parameter δ(n)—this is the maximal fraction of corrupted codeword bits for which a (2-query) decoder can recover correctly every message bit (with high probability). Our combinatorial lemma gives non-trivial rate bounds for any corruption parameter δ(n) such that δ(n) · n = ω(1), whereas the previous lemma works only for corruption parameter δ(n) such that δ(n) · n ≥ log n. The study of LDCs with sublinear corruption parameter is also motivated by Dvir’s (IEEE conference on computational complexity. IEEE Computer Society, pp 291–298, 2010) observation that sufficiently strong bounds on the rate of such LDCs imply explicit constructions of rigid matrices.
Ending Page	309
Page Count	43
Starting Page	267
File Format	PDF
ISSN	10163328
e-ISSN	14208954
Journal	Computational complexity
Issue Number	2
Volume Number	21
Language	English
Publisher	SP Birkhäuser Verlag Basel
Publisher Date	2012-04-27
Publisher Place	Basel
Access Restriction	One Nation One Subscription (ONOS)
Subject Keyword	Locally testable codes locally decodable codes Computational Mathematics and Numerical Analysis Bounds on codes Linear codes, general Algorithm Analysis and Problem Complexity lower bounds
Content Type	Text
Resource Type	Article
Subject	Theoretical Computer Science Computational Theory and Mathematics Computational Mathematics

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

Towards Lower Bounds on Locally Testable Codes via Density Arguments

Lower bounds for linear locally decodable codes and private information retrieval

On Matrix Rigidity and Locally Self-correctable Codes

Composition of semi-LTCs by two-wise tensor products

Sparse affine-invariant linear codes are locally testable

Three-Query Locally Decodable Codes with Higher Correctness Require Exponential Length

Query-Efficient Locally Decodable Codes of Subexponential Length

2-Transitivity is Insufficient for Local Testability

Property Testing Lower Bounds via Communication Complexity

Towards lower bounds on locally testable codes via density arguments

Similar Documents

Towards Lower Bounds on Locally Testable Codes via Density Arguments

Lower bounds for linear locally decodable codes and private information retrieval

On Matrix Rigidity and Locally Self-correctable Codes

Composition of semi-LTCs by two-wise tensor products

Sparse affine-invariant linear codes are locally testable

Three-Query Locally Decodable Codes with Higher Correctness Require Exponential Length

Query-Efficient Locally Decodable Codes of Subexponential Length

2-Transitivity is Insufficient for Local Testability

Property Testing Lower Bounds via Communication Complexity

Towards lower bounds on locally testable codes via density arguments