Query complexity lower bounds for local list-decoding and hard-core predicates (even for small rate
summary
Proves query lower bounds for local list decoding of very low‑rate binary codes and shows these bounds hold even for exponentially large lists. Main quantitative claims: for half-minus-epsilon error radius any local list decoder needs omega(1/epsilon^2) queries when epsilon ≥ 1/poly(K) (matching Goldreich–Levin), and at small epsilon the paper gives an omega(1/√epsilon) lower bound. Proof reduces decoding to a randomized approximate task and embeds it into an AC0 coin problem circuit lower bound to get the query tradeoffs.
AI-written summary · about