TY - GEN

T1 - An Exponential Lower Bound for Linear 3-Query Locally Correctable Codes

AU - Kothari, Pravesh K.

AU - Manohar, Peter

N1 - Publisher Copyright:
© 2024 Owner/Author.

PY - 2024/6/10

Y1 - 2024/6/10

N2 - We prove that the blocklength n of a linear 3-query locally correctable code (LCC) L : Fk → Fn with distance δmust be at least n ≥ 2ω((δ2 k/(|F|-1)2)1/8). In particular, the blocklength of a linear 3-query LCC with constant distance over any small field grows exponentially with k. This improves on the best prior lower bound of n ≥ ω(k3), which holds even for the weaker setting of 3-query locally decodable codes (LDCs), and comes close to matching the best-known construction of 3-query LCCs based on binary Reed-Muller codes, which achieve n ≤ 2O(k1/2). Because there is a 3-query LDC with a strictly subexponential blocklength, as a corollary we obtain the first strong separation between q-query LCCs and LDCs for any constant q ≥ 3. Our proof is based on a new upgrade of the method of spectral refutations via Kikuchi matrices developed in recent works that reduces establishing (non-)existence of combinatorial objects to proving unsatisfiability of associated XOR instances. Our key conceptual idea is to apply this method with XOR instances obtained via long-chain derivations - a structured variant of low-width resolution for XOR formulas from proof complexity.

AB - We prove that the blocklength n of a linear 3-query locally correctable code (LCC) L : Fk → Fn with distance δmust be at least n ≥ 2ω((δ2 k/(|F|-1)2)1/8). In particular, the blocklength of a linear 3-query LCC with constant distance over any small field grows exponentially with k. This improves on the best prior lower bound of n ≥ ω(k3), which holds even for the weaker setting of 3-query locally decodable codes (LDCs), and comes close to matching the best-known construction of 3-query LCCs based on binary Reed-Muller codes, which achieve n ≤ 2O(k1/2). Because there is a 3-query LDC with a strictly subexponential blocklength, as a corollary we obtain the first strong separation between q-query LCCs and LDCs for any constant q ≥ 3. Our proof is based on a new upgrade of the method of spectral refutations via Kikuchi matrices developed in recent works that reduces establishing (non-)existence of combinatorial objects to proving unsatisfiability of associated XOR instances. Our key conceptual idea is to apply this method with XOR instances obtained via long-chain derivations - a structured variant of low-width resolution for XOR formulas from proof complexity.

KW - Kikuchi Matrices

KW - Locally Correctable Codes

KW - Locally Decodable Codes

UR - http://www.scopus.com/inward/record.url?scp=85196645174&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85196645174&partnerID=8YFLogxK

U2 - 10.1145/3618260.3649640

DO - 10.1145/3618260.3649640

M3 - Conference contribution

AN - SCOPUS:85196645174

T3 - Proceedings of the Annual ACM Symposium on Theory of Computing

SP - 776

EP - 787

BT - STOC 2024 - Proceedings of the 56th Annual ACM Symposium on Theory of Computing

A2 - Mohar, Bojan

A2 - Shinkar, Igor

A2 - O�Donnell, Ryan

PB - Association for Computing Machinery

T2 - 56th Annual ACM Symposium on Theory of Computing, STOC 2024

Y2 - 24 June 2024 through 28 June 2024

ER -