Document Open Access Logo

Combinatorial Lower Bounds for 3-Query LDCs

Authors Arnab Bhattacharyya, L. Sunil Chandran, Suprovat Ghoshal

PDF

File

Thumbnail PDF
PDF
LIPIcs.ITCS.2020.85.pdf
  • Filesize: 478 kB
  • 8 pages

Document Identifiers

Subject Classification

ACM Subject Classification
  • Theory of computation → Error-correcting codes
Keywords
  • Coding theory
  • Graph theory
  • Hypergraphs

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Abstract

A code is called a q-query locally decodable code (LDC) if there is a randomized decoding algorithm that, given an index i and a received word w close to an encoding of a message x, outputs x_i by querying only at most q coordinates of w. Understanding the tradeoffs between the dimension, length and query complexity of LDCs is a fascinating and unresolved research challenge. In particular, for 3-query binary LDC’s of dimension k and length n, the best known bounds are: 2^{k^o(1)} ≥ n ≥ Ω ̃(k²).
In this work, we take a second look at binary 3-query LDCs. We investigate a class of 3-uniform hypergraphs that are equivalent to strong binary 3-query LDCs. We prove an upper bound on the number of edges in these hypergraphs, reproducing the known lower bound of Ω ̃(k²) for the length of strong 3-query LDCs. In contrast to previous work, our techniques are purely combinatorial and do not rely on a direct reduction to 2-query LDCs, opening up a potentially different approach to analyzing 3-query LDCs.

Cite As Get BibTex

Arnab Bhattacharyya, L. Sunil Chandran, and Suprovat Ghoshal. Combinatorial Lower Bounds for 3-Query LDCs. In 11th Innovations in Theoretical Computer Science Conference (ITCS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 151, pp. 85:1-85:8, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020) https://doi.org/10.4230/LIPIcs.ITCS.2020.85

Author Details

Arnab Bhattacharyya
  • National University of Singapore, Singapore
L. Sunil Chandran
  • Indian Institute of Science, Bangalore, India
Suprovat Ghoshal
  • Indian Institute of Science, Bangalore, India

Funding

  • Bhattacharyya, Arnab: Partially supported by NUS Startup Grant R-252-000-A33-133.

Acknowledgements

AB thanks Sivakanth Gopi, Nikhil Srivastava, and Luca Trevisan for many useful discussions about this problem.

References

  1. Laszlo Babai, Lance Fortnow, Leonid Levin, and Mario Szegedy. Checking computations in polylogarithmic time. In Proceedings of the 23rd Annual ACM Symposium on Theory of Computing, pages 21-31, 1991. Google Scholar
  2. Boaz Barak, Zeev Dvir, Amir Yehudayoff, and Avi Wigderson. Rank bounds for design matrices with applications to combinatorial geometry and locally correctable codes. In Proceedings of the 43rd annual ACM symposium on Theory of computing, pages 519-528. ACM, 2011. Google Scholar
  3. Benny Chor, Eyal Kushilevitz, Oded Goldreich, and Madhu Sudan. Private information retrieval. Journal of the ACM (JACM), 45(6):965-981, 1998. Google Scholar
  4. D Dellamonica, P Haxell, Tomasz Łuczak, Dhruv Mubayi, Brendan Nagle, Yury Person, Vojtech Rödl, Mathias Schacht, and Jacques Verstraëte. On even-degree subgraphs of linear hypergraphs. Combinatorics, Probability and Computing, 21(1-2):113-127, 2012. Google Scholar
  5. Zeev Dvir, Parikshit Gopalan, and Sergey Yekhanin. Matching vector codes. SIAM Journal on Computing, 40(4):1154-1178, 2011. Google Scholar
  6. Zeev Dvir, Shubhangi Saraf, and Avi Wigderson. Breaking the quadratic barrier for 3-LCC’s over the reals. In Proceedings of the 46th Annual ACM Symposium on Theory of Computing, pages 784-793. ACM, 2014. Google Scholar
  7. Zeev Dvir, Shubhangi Saraf, and Avi Wigderson. Improved rank bounds for design matrices and a new proof of Kelly’s theorem. In Forum of Mathematics, Sigma, volume 2, page e4. Cambridge Univ Press, 2014. Google Scholar
  8. Zeev Dvir and Amir Shpilka. Locally decodable codes with two queries and polynomial identity testing for depth 3 circuits. sicomp, 36(5):1404-1434, 2007. Google Scholar
  9. Klim Efremenko. 3-query locally decodable codes of subexponential length. SIAM Journal on Computing, 41(6):1694-1703, 2012. Google Scholar
  10. Jonathan Katz and Luca Trevisan. On the efficiency of local decoding procedures for error-correcting codes. In Proceedings of the 32nd annual ACM symposium on Theory of Computing, pages 80-86. ACM, 2000. Google Scholar
  11. Neeraj Kayal and Shubhangi Saraf. Blackbox polynomial identity testing for depth 3 circuits. In Proceedings of the 50th annual IEEE symposium on Foundations of Computer Science, pages 198-207. IEEE, 2009. Google Scholar
  12. Iordanis Kerenidis and Ronald de Wolf. Exponential lower bound for 2-query locally decodable codes via a quantum argument. In Proceedings of the thirty-fifth annual ACM symposium on Theory of computing, pages 106-115. ACM, 2003. Google Scholar
  13. Madhu Sudan, Luca Trevisan, and Salil Vadhan. Pseudorandom Generators without the XOR Lemma. Journal of Computer and System Sciences, 62(2):236-266, 2001. Google Scholar
  14. David Woodruff. New lower bounds for general locally decodable codes. In Electronic Colloquium on Computational Complexity (ECCC), number 006 in 14, 2007. Google Scholar
  15. David P. Woodruff. A Quadratic Lower Bound for Three-Query Linear Locally Decodable Codes over Any Field. Journal of Computer Science Technology, 27(4):678-686, 2012. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2025 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact