Please use this identifier to cite or link to this item:
https://doi.org/10.4230/LIPIcs.ITCS.2020.85
DC Field | Value | |
---|---|---|
dc.title | Combinatorial Lower Bounds for 3-Query LDCs | |
dc.contributor.author | Bhattacharyya, Arnab | |
dc.contributor.author | Chandran, L Sunil | |
dc.contributor.author | Ghoshal, Suprovat | |
dc.date.accessioned | 2020-07-27T07:10:57Z | |
dc.date.available | 2020-07-27T07:10:57Z | |
dc.date.issued | 2020-01-01 | |
dc.identifier.citation | Bhattacharyya, Arnab, Chandran, L Sunil, Ghoshal, Suprovat (2020-01-01). Combinatorial Lower Bounds for 3-Query LDCs. Leibniz International Proceedings in Informatics, LIPIcs 151 : 85:1-85:1. ScholarBank@NUS Repository. https://doi.org/10.4230/LIPIcs.ITCS.2020.85 | |
dc.identifier.isbn | 9783959771344 | |
dc.identifier.issn | 18688969 | |
dc.identifier.uri | https://scholarbank.nus.edu.sg/handle/10635/171714 | |
dc.description.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 xi 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: 2ko(1) ≥ n ≥ Ω (k2). 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 Ω (k2) 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. © Arnab Bhattacharyya, L. Sunil Chandran, and Suprovat Ghoshal. | |
dc.publisher | Schloss Dagstuhl - Leibniz-Zentrum für Informatik | |
dc.source | Elements | |
dc.type | Conference Paper | |
dc.date.updated | 2020-07-24T12:00:07Z | |
dc.contributor.department | DEPARTMENT OF COMPUTER SCIENCE | |
dc.description.doi | 10.4230/LIPIcs.ITCS.2020.85 | |
dc.description.sourcetitle | Leibniz International Proceedings in Informatics, LIPIcs | |
dc.description.volume | 151 | |
dc.description.page | 85:1-85:1 | |
dc.published.state | Published | |
Appears in Collections: | Elements Staff Publications |
Show simple item record
Files in This Item:
File | Description | Size | Format | Access Settings | Version | |
---|---|---|---|---|---|---|
ldc-submit.pdf | Published version | 501.23 kB | Adobe PDF | OPEN | Published | View/Download |
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.