A binary code $\text{Enc}:\{0,1\}^k \rightarrow \{0,1\}^n$ is $(\frac{1}{2}-\varepsilon,L)$-list decodable if for every $w \in \{0,1\}^n$, there exists a set $\text{List}(w)$ of size at most $L$, containing all messages $m \in \{0,1\}^k$ such that the relative Hamming distance between $\text{Enc}(m)$ and $w$ is at most $\frac{1}{2}-\varepsilon$.
A $q$-query local list-decoder is a randomized procedure 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, $\text{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 $\text{Enc}$ is small (meaning that $n \ge 2^{k}$):

* For $\varepsilon = 1/k^{\nu}$ for some constant $\nu>0$, we prove a lower bound of $q=\Omega(\frac{\log(1/\delta)}{\varepsilon^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)}{\varepsilon^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^{\nu}}$ and the number of coins tossed by $\text{Dec}$ is small (and therefore does not apply to the Hadamard code, or other codes with low rate).

* For smaller $\varepsilon$, we prove a lower bound of roughly $q = \Omega(\frac{1}{\sqrt{\varepsilon}})$. 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 $\varepsilon$.

Local list-decoders with small $\varepsilon$ form the key component in the celebrated theorem of Goldreich and Levin that extracts a hard-core predicate from a one-way function.
We show that black-box proofs cannot improve the Goldreich-Levin theorem and produce a hard-core predicate that is hard to predict with probability $\frac{1}{2}+\frac{1}{\ell^{\omega(1)}}$ when provided with a one-way function $f:\{0,1\}^{\ell} \rightarrow \{0,1\}^{\ell}$, such that circuits of size $\text{poly}(\ell)$ cannot invert $f$ with probability $\rho=1/2^{\sqrt{\ell}}$ (or even $\rho=1/2^{\Omega(\ell)}$). This limitation applies to any proof by black-box reduction (even if the reduction is allowed to use nonuniformity and has oracle access to $f$).