A Near-Cubic Lower Bound for 3-Query Locally Decodable Codes from Semirandom CSP Refutation
A Near-Cubic Lower Bound for 3-Query Locally Decodable Codes from Semirandom CSP Refutation
复制标题
来自半随机 CSP 反驳的 3 查询本地可解码代码的近三次下界
DOI：
10.1145/3564246.3585143
复制
发表时间：
2023
期刊：
影响因子：
--
通讯作者：
Manohar, Peter
中科院分区：
文献类型：
--
作者：
Alrabiah, Omar;Guruswami, Venkatesan;Kothari, Pravesh K.;Manohar, Peter
如果可以通过随机查询最多 q 个坐标上的编码 x=C(b) 来以良好的置信度恢复消息 b ∈ {0,1}k 的任何选定位 bi，则代码 C∶{0,1}k→{0,1} 是一个 q 本地可解码代码（q-LDC）。现有的 2-LDC 结构实现 = exp(O(k))，下限表明这实际上是严格的。然而，当q= 3时，我们所知甚少：实现的最佳构造= exp(ko(1))，而最知名的结果仅显示块长度上的二次下界n≥ Ω(k2/log(k))。在本文中，我们证明了3查询LDC的块长度上的近三次下界n≥ Ω(k3/log6(k))。这改进了多项式因子墨水的最著名的现有工作。我们的证明依赖于最不发达国家之间的新联系，并反驳有限随机性的约束满足问题。我们的定量改进建立在反驳 CSP 半随机实例的新技术的基础上，特别是依赖于限制适当的 Kikuchi 矩阵的谱范数。
A codeC∶ {0,1}k→ {0,1}nis aq-locally decodable code (q-LDC) if one can recover any chosen bitbiof the messageb∈ {0,1}kwith good confidence by randomly querying the encodingx=C(b) on at mostqcoordinates. Existing constructions of 2-LDCs achieven= exp(O(k)), and lower bounds show that this is in fact tight. However, whenq= 3, far less is known: the best constructions achieven= exp(ko(1)), while the best known results only show a quadratic lower boundn≥ Ω(k2/log(k)) on the blocklength.In this paper, we prove a near-cubic lower bound ofn≥ Ω(k3/log6(k)) on the blocklength of 3-query LDCs. This improves on the best known prior works by a polynomial factor ink. 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.
登录
查看更多内容
大字母表上 2 查询 LCC 的下界
DOI：
10.4230/lipics.approx-random.2017.30
发表时间：
2016
期刊：
Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing
影响因子：
--
作者：
Arnab Bhattacharyya;Sivakanth Gopi;Avishay Tal
通讯作者：
Avishay Tal
影响因子：
1.6
作者：
Victor Chen;E. Grigorescu;Ronald de Wolf
通讯作者：
Ronald de Wolf
DOI：
10.1007/978-3-540-24676-3_26
发表时间：
2004
期刊：
SubStance
影响因子：
--
作者：
Yuval Ishai;E. Kushilevitz
通讯作者：
E. Kushilevitz
超图摩尔界的简单而清晰的证明
DOI：
10.48550/arxiv.2207.10850
发表时间：
2022
期刊：
ArXiv
影响因子：
--
作者：
Jun;Pravesh Kothari;Sidhanth Mohanty
通讯作者：
Sidhanth Mohanty
反驳
DOI：
10.2307/3685398
发表时间：
2004
期刊：
SubStance
影响因子：
--
作者：
L. Salvayre;R. Lapidus
通讯作者：
R. Lapidus