@online{RonZewi2409.01708,
TITLE = {Query Complexity Lower Bounds for Local List-Decoding and Hard-Core Predicates (Even for Small Rate and Huge Lists)},
AUTHOR = {Ron-Zewi, Noga and Shaltiel, Ronen and Varma, Nithin},
LANGUAGE = {eng},
URL = {https://arxiv.org/abs/2409.01708},
EPRINT = {2409.01708},
EPRINTTYPE = {arXiv},
YEAR = {2024},
MARGINALMARK = {$\bullet$},
ABSTRACT = {A binary code Enc$:\{0,1\}^k \to \{0,1\}^n$ is $(0.5-\epsilon,L)$-list
decodable if for all $w \in \{0,1\}^n$, the set List$(w)$ of all messages $m
\in \{0,1\}^k$ such that the relative Hamming distance between Enc$(m)$ and $w$
is at most $0.5 -\epsilon$, has size at most $L$. Informally, a $q$-query local
list-decoder for Enc is a randomized procedure Dec$:[k]\times [L] \to \{0,1\}$
that when given oracle access to a string $w$, makes at most $q$ oracle calls,
and for every message $m \in \text{List}(w)$, with high probability, there
exists $j \in [L]$ such that for every $i \in [k]$, with high probability,
Dec$^w(i,j)=m_i$.
We prove lower bounds on $q$, that apply even if $L$ is huge (say
$L=2^{k^{0.9}}$) and the rate of Enc is small (meaning that $n \ge 2^{k}$):
1. For $\epsilon \geq 1/k^{\nu}$ for some universal constant $0< \nu < 1$, we
prove a lower bound of $q=\Omega(\frac{\log(1/\delta)}{\epsilon^2})$, where
$\delta$ is the error probability of the local list-decoder. This bound is
tight as there is a matching upper bound by Goldreich and Levin (STOC 1989) of
$q=O(\frac{\log(1/\delta)}{\epsilon^2})$ for the Hadamard code (which has
$n=2^k$). This bound extends an earlier work of Grinberg, Shaltiel and Viola
(FOCS 2018) which only works if $n \le 2^{k^{\gamma}}$ for some universal
constant $0<\gamma <1$, and the number of coins tossed by Dec is small (and
therefore does not apply to the Hadamard code, or other codes with low rate).
2. For smaller $\epsilon$, we prove a lower bound of roughly $q =
\Omega(\frac{1}{\sqrt{\epsilon}})$. To the best of our knowledge, this is the
first lower bound on the number of queries of local list-decoders that gives $q
\ge k$ for small $\epsilon$.
We also prove black-box limitations for improving some of the parameters of
the Goldreich-Levin hard-core predicate construction.
},
}