Query complexity lower bounds for local list-decoding and hard-core predicates (even for small rate and huge lists)

Noga Ron-Zewi, Ronen Shaltiel, Nithin Varma

A binary code Enc$:\{0,1{\}}^k\to \{0,1{\}}^n$ is $(0.5-\hat{I}\mu ,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…