TY - GEN

T1 - A Near-Cubic Lower Bound for 3-Query Locally Decodable Codes from Semirandom CSP Refutation

AU - Alrabiah, Omar

AU - Guruswami, Venkatesan

AU - Kothari, Pravesh K.

AU - Manohar, Peter

N1 - Publisher Copyright:
© 2023 Owner/Author.

PY - 2023/6/2

Y1 - 2023/6/2

N2 - A code C ¶ {0,1}k → {0,1}n is a q-locally decodable code (q-LDC) if one can recover any chosen bit bi of the message b {0,1}k with good confidence by randomly querying the encoding x = C(b) on at most q coordinates. Existing constructions of 2-LDCs achieve n = exp(O(k)), and lower bounds show that this is in fact tight. However, when q = 3, far less is known: the best constructions achieve n = exp(ko(1)), while the best known results only show a quadratic lower bound n ≥ ω(k2/log(k)) on the blocklength. In this paper, we prove a near-cubic lower bound of n ≥ ω(k3/log6(k)) on the blocklength of 3-query LDCs. This improves on the best known prior works by a polynomial factor in k. Our proof relies on a new connection between LDCs and refuting constraint satisfaction problems with limited randomness. Our quantitative improvement builds on the new techniques for refuting semirandom instances of CSPs and, in particular, relies on bounding the spectral norm of appropriate Kikuchi matrices.

AB - A code C ¶ {0,1}k → {0,1}n is a q-locally decodable code (q-LDC) if one can recover any chosen bit bi of the message b {0,1}k with good confidence by randomly querying the encoding x = C(b) on at most q coordinates. Existing constructions of 2-LDCs achieve n = exp(O(k)), and lower bounds show that this is in fact tight. However, when q = 3, far less is known: the best constructions achieve n = exp(ko(1)), while the best known results only show a quadratic lower bound n ≥ ω(k2/log(k)) on the blocklength. In this paper, we prove a near-cubic lower bound of n ≥ ω(k3/log6(k)) on the blocklength of 3-query LDCs. This improves on the best known prior works by a polynomial factor in k. Our proof relies on a new connection between LDCs and refuting constraint satisfaction problems with limited randomness. Our quantitative improvement builds on the new techniques for refuting semirandom instances of CSPs and, in particular, relies on bounding the spectral norm of appropriate Kikuchi matrices.

KW - CSP refutation

KW - Locally decodable codes

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

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

U2 - 10.1145/3564246.3585143

DO - 10.1145/3564246.3585143

M3 - Conference contribution

AN - SCOPUS:85163060195

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

SP - 1438

EP - 1448

BT - STOC 2023 - Proceedings of the 55th Annual ACM Symposium on Theory of Computing

A2 - Saha, Barna

A2 - Servedio, Rocco A.

PB - Association for Computing Machinery

T2 - 55th Annual ACM Symposium on Theory of Computing, STOC 2023

Y2 - 20 June 2023 through 23 June 2023

ER -