  We introduce a novel family of expander-based error correcting codes. These
codes can be sampled with randomness linear in the block-length, and achieve
list-decoding capacity (among other local properties). Our expander-based codes
can be made starting from any family of sufficiently low-bias codes, and as a
consequence, we give the first construction of a family of algebraic codes that
can be sampled with linear randomness and achieve list-decoding capacity. We
achieve this by introducing the notion of a pseudorandom puncturing of a code,
where we select $n$ indices of a base code $C\subset \mathbb{F}_q^m$ via an
expander random walk on a graph on $[m]$. Concretely, whereas a random linear
code (i.e. a truly random puncturing of the Hadamard code) requires $O(n^2)$
random bits to sample, we sample a pseudorandom linear code with $O(n)$ random
bits. We show that pseudorandom puncturings satisfy several desirable
properties exhibited by truly random puncturings. In particular, we extend a
result of (Guruswami Mosheiff FOCS 2022) and show that a pseudorandom
puncturing of a small-bias code satisfies the same local properties as a random
linear code with high probability. As a further application of our techniques,
we also show that pseudorandom puncturings of Reed Solomon codes are
list-recoverable beyond the Johnson bound, extending a result of (Lund
Potukuchi RANDOM 2020). We do this by instead analyzing properties of codes
with large distance, and show that pseudorandom puncturings still work well in
this regime.
