We present simple constructions of good approxi-mate locally decodable codes (ALDCs) in the presence of a$\delta{-}$fraction of errors for$\delta < 1/2$. In a standard locally decodable code$C:\Sigma_{1}^{k}\rightarrow\Sigma_{2}^{n}$, there is a decoder$M$that on input$i\in[k]$correctly outputs the i-th symbol of a message$x$(with high probability) using only$q$queries to a given string$w$that is$\Delta$-close to$C(x)$. In an ALDC, the decoder$M$only needs to be correct on a 1$-\varepsilon$fraction of$i\in[k]$for$\varepsilon$much smaller than$\delta$. We present a construction of explicit ALDCs for all constants 1/2$> \delta > \varepsilon$with a constant number of queries$q$and with constant, near-optimal rate. Standard LDCs with constant number of queries and any constant rate are known to be impossible. We additionally explore what is the lowest error probability$\varepsilon$one can achieve for fixed$\delta$and$q$. We show that for any ALDC,$\in=\Omega(\delta \mathrm{r}q/2\rceil)$. We then show that there exist explicit constant rate ALDCs for any constant$q$that achieve$\varepsilon=O(\delta^{\lceil q/2\rceil})$. In particular, for$q=3$, we have a constant rate ALDC with error probability$\varepsilon=O(\delta^{2})$. A full version of this paper is available at https://eccc.weizmann.ac.il/report/2023/056/.

A Chor–Goldreich (CG) source is a sequence of random variables X = X1 ∘ … ∘ Xt, where each Xi ∼ {0,1}d and Xi has δ d min-entropy conditioned on any fixing of X1 ∘ … ∘ Xi−1. The parameter 0<δ≤ 1 is the entropy rate of the source. We typically think of d as constant and t as growing. We extend this notion in several ways, defining almost CG sources. Most notably, we allow each Xi to only have conditional Shannon entropy δ d.

Existing proofs that deduce BPP = P from circuit lower bounds convert randomized algorithms into deterministic algorithms with a large polynomial slowdown. We convert randomized algorithms into deterministic ones with little slowdown . Specifically, assuming exponential lower bounds against randomized NP ∩ coNP circuits, formally known as randomized SVN circuits, we convert any randomized algorithm over inputs of length n running in time t ≥ n into a deterministic one running in time t 2+α for an arbitrarily small constant α > 0. Such a slowdown is nearly optimal for t close to n , since under standard complexity-theoretic assumptions, there are problems with an inherent quadratic derandomization slowdown. We also convert any randomized algorithm that errs rarely into a deterministic algorithm having a similar running time (with pre-processing). The latter derandomization result holds under weaker assumptions, of exponential lower bounds against deterministic SVN circuits. Our results follow from a new, nearly optimal, explicit pseudorandom generator fooling circuits of size s with seed length (1+α)log s , under the assumption that there exists a function f ∈ E that requires randomized SVN circuits of size at least 2 (1-α′) n , where α = O (α)′. The construction uses, among other ideas, a new connection between pseudoentropy generators and locally list recoverable codes.

Existing proofs that deduce BPP = P from circuit lower bounds convert randomized algorithms into deterministic algorithms with a large polynomial slowdown. We convert randomized algorithms into deterministic ones with little slowdown. Specifically, assuming exponential lower bounds against randomized single-valued nondeterministic (SVN) circuits, we convert any randomized algorithm over inputs of length n running in time t ≥ n to a deterministic one running in time t2+αfor an arbitrarily small constant . Such a slowdown is nearly optimal, as, under complexity-theoretic assumptions, there are problems with an inherent quadratic derandomization slowdown. We also convert any randomized algorithm that errs rarely into a deterministic algorithm having a similar running time (with pre-processing). The latter derandomization result holds under weaker assumptions, of exponential lower bounds against deterministic SVN circuits. Our results follow from a new, nearly optimal, explicit pseudorandom generator fooling circuits of size s with seed length (1 + α)log s, under the assumption that there exists a function f ϵ E that requires randomized SVN circuits of size at least 2(1-α')n, where. α=O(α'). The construction uses, among other ideas, a new connection between pseudoentropy generators and locally list recoverable codes.

The long code is a central tool in hardness of approximation, especially in questions related to the unique games conjecture. We construct a new code that is exponentially more efficient, but can still be used in many of these applications. Using the new code we obtain exponential improvements over several known results, including the following: 1. For any eps > 0, we show the existence of an n vertex graph G where every set of o(n) vertices has expansion 1 - eps, but G's adjacency matrix has more than exp(log^delta n) eigenvalues larger than 1 - eps, where delta depends only on eps. This answers an open question of Arora, Barak and Steurer (FOCS 2010) who asked whether one can improve over the noise graph on the Boolean hypercube that has poly(log n) such eigenvalues. 2. A gadget that reduces unique games instances with linear constraints modulo K into instances with alphabet k with a blowup of K^polylog(K), improving over the previously known gadget with blowup of 2^K. 3. An n variable integrality gap for Unique Games that that survives exp(poly(log log n)) rounds of the SDP + Sherali Adams hierarchy, improving on the previously known bound of poly(log log n). We show a connection between the local testability of linear codes and small set expansion in certain related Cayley graphs, and use this connection to derandomize the noise graph on the Boolean hypercube.