Combinatorial lower bounds for 3-query LDCs

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 betwe...

Full description

Saved in:
Bibliographic Details
Published in:arXiv.org 2019-11
Main Authors: Bhattacharyya, Arnab, L Sunil Chandran, Ghoshal, Suprovat
Format: Article
Language:English
Subjects:
Algorithms
Combinatorial analysis
Decoding
Direct reduction
Graph theory
Graphs
Lower bounds
Queries
Upper bounds
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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 LDCs of dimension \(k\) and length \(n\), the best known bounds are: \(2^{k^{o(1)}} \geq n \geq \tilde{\Omega}(k^2)\). 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 \(\tilde{\Omega}(k^2)\) 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.
ISSN:2331-8422