# Punctured Low-Bias Codes Behave Like Random Linear Codes

Venkatesan Guruswami

University of California, Berkeley
<EMAIL_ADDRESS>Jonathan Mosheiff

Ben-Gurion University
<EMAIL_ADDRESS>
###### Abstract

Random linear codes are a workhorse in coding theory, and are used to show the
existence of codes with the best known or even near-optimal trade-offs in many
noise models. However, they have little structure besides linearity, and are
not amenable to tractable error-correction algorithms.

In this work, we prove a general derandomization result applicable to random
linear codes. Namely, in settings where the coding-theoretic property of
interest is “local” (in the sense of forbidding certain bad configurations
involving few vectors—code distance and list-decodability being notable
examples), one can replace random linear codes (RLCs) with a significantly
derandomized variant with essentially no loss in parameters. Specifically,
instead of randomly sampling coordinates of the (long) Hadamard code (which is
an equivalent way to describe RLCs), one can randomly sample coordinates of
any code with low bias. Over large alphabets, the low bias requirement can be
weakened to just large distance. Furthermore, large distance suffices even
with a small alphabet in order to match the current best known bounds for RLC
list-decodability.

In particular, by virtue of our result, all current (and future) achievability
bounds for list-decodability of random linear codes extend _automatically_ to
random puncturings of any low-bias (or large alphabet) “mother” code. We also
show that our punctured codes emulate the behavior of RLCs on stochastic
channels, thus giving a derandomization of RLCs in the context of achieving
Shannon capacity as well. Thus, we have a randomness-efficient way to sample
codes achieving capacity in both worst-case and stochastic settings that can
further inherit algebraic or other algorithmically useful structural
properties of the mother code.

††footnotetext: Research supported in part by NSF grants CCF-1814603 and
CCF-1908125, and a Simons Investigator Award. Any opinions, findings, and
conclusions or recommendations expressed in this material are those of the
author(s) and do not necessarily reflect the views of the National Science
Foundation.

###### Contents

  1. 1 Introduction
    1. 1.1 Previous work
    2. 1.2 On an error in a previous version of this paper regarding RS codes
  2. 2 Main Results
    1. 2.1 A framework for studying properties of codes
    2. 2.2 Theorem A: Randomly punctured low-bias codes
    3. 2.3 Applications of Theorem 1 for list-decodability
    4. 2.4 Derandomization of RLCs
    5. 2.5 Theorem B: Randomly punctured codes of near-optimal distance
    6. 2.6 Theorem C: Randomly punctured codes in the stochastic error model
    7. 2.7 Organization
  3. 3 Technical overview
  4. 4 Preliminaries
    1. 4.1 General notation
    2. 4.2 A characterization of list-decodable linear codes
    3. 4.3 The scalar-multiplied code $\Lambda\mathcal{C}$ and scalar-expanded code $\mathcal{D}^{*}$
    4. 4.4 Fourier transform
    5. 4.5 Entropy and KL-divergence
    6. 4.6 The empirical distribution of the rows of a matrix
  5. 5 A random puncturing of a near-optimal-distance code is likely to be list-decodable
    1. 5.1 GHK list-decodability bound for random linear codes revisited
    2. 5.2 Proof of Theorem 5
    3. 5.3 Proof of Lemma 5.6
  6. 6 Random puncturings of certain codes are locally-similar to RLCs
    1. 6.1 Monotone-increasing properties and minimal sets
    2. 6.2 Row-symmetric $b$-local properties in terms of distributions over ${\mathbb{F}}_{q}^{b}$
    3. 6.3 List-recoverability as a property of codes
    4. 6.4 Proof of Theorems 1 and 4
  7. 7 Derandomization of RLCs
  8. 8 Random puncturings of low-bias codes achieve capacity versus memoryless additive noise

##  1 Introduction

Random linear codes (RLCs) are ubiquitous in coding theory, serving as a
fundamental building block in the construction of codes since the works of
Shannon. RLCs are extensively studied, and known to enjoy excellent
combinatorial properties. In particular, they achieve Shannon capacity, the
Gilbert-Varshamov rate vs. distance trade-off, and are list-decodable up to
capacity.

An RLC of length $n$ and rate111More accurately, $R$ is the design rate of the
code. The actual rate, $\frac{\operatorname{rank}A}{n}$, equals $R$ if and
only if $A$ is of full rank—an event which holds with very high probability.
See Lemma 2.3 for more details. $0<R<1$ over alphabet ${\mathbb{F}}_{q}$ is
the row span of a matrix $A$, sampled uniformly from
${\mathbb{F}}_{q}^{k\times n}$, where $k=Rn$. Here, ${\mathbb{F}}_{q}$ denotes
the finite field of order $q$. Equivalently, one can think of $A$ as a matrix
with $n$ random independent columns, each sampled uniformly from
${\mathbb{F}}_{q}^{k}$.

In this work we study derandomizations of RLCs. Specifically, we consider a
code $\mathcal{C}$ generated by a matrix whose columns are independently
sampled from some distribution $\mu$, where the support of $\mu$ is a much
smaller set than ${\mathbb{F}}_{q}^{k}$ (possibly exponentially so). We are
able to prove that, under fairly modest and general assumptions on $\mu$, this
random code $\mathcal{C}$ is similar to an RLC with respect to _local
properties_ , a notion which will soon be explained. A special case of this
result is that $\mathcal{C}$ is very likely to achieve _list-decoding
capacity_ , since RLCs are known to do so (in fact, the convergence of RLCs to
list-decoding capacity has been extensively studied). Independently of this
result, we also show that, similarly to an RLC, $\mathcal{C}$ is likely to
achieve capacity with regard to every memoryless additive-noise channel.

To describe our result more formally, we turn to the notion of punctured
codes. Puncturing is a basic operation by which new codes are constructed from
existing ones. A puncturing of a code
$\mathcal{D}\subseteq{\mathbb{F}}_{q}^{m}$ is a code
$\mathcal{C}\subseteq{\mathbb{F}}_{q}^{n}$ (where we usually think of $m$ as
being much large than $n$) whose coordinates are taken from those of
$\mathcal{D}$. More precisely, $\mathcal{C}$ is a puncturing of $\mathcal{D}$
if $\mathcal{C}=\\{\left(x_{i_{1}},\dots,x_{i_{n}}\right)\mid
x=\left(x_{1}\dots x_{m}\right)\in\mathcal{D}\\}$, for some integers
$i_{1},\dots,i_{n}\in[m]$. We sometimes refer to $\mathcal{D}$ as the _mother
code_. When $i_{1},\dots,i_{n}$ are sampled uniformly and independently from
$[m]$, we say that $\mathcal{C}$ is a random $n$-puncturing of $\mathcal{D}$.
Puncturing generally increases the rate of a code, and we often take
$\mathcal{D}$ to be a code of rate approaching $0$, while the rate of
$\mathcal{C}$ is a constant in $(0,1)$.

An equivalent way to describe an RLC of length $n$ and rate $R$ is as a random
puncturing of the _Hadamard code_ 222The Hadamard code of length $q^{k}$ over
alphabet ${\mathbb{F}}_{q}$ is $\left\\{\left(\left\langle
x,y\right\rangle\right)_{y\in{\mathbb{F}}_{q}^{k}}\mid
x\in{\mathbb{F}}_{q}^{k}\right\\}$. of length $q^{k}$ (where $k=Rn$). The
Hadamard code has very poor rate. Consequently, to obtain a punctured code of
length $n$ and constant rate from a Hadamard mother code, the mother code must
be taken to have length exponential in $n$. Our motivating question is
whether, in this construction, one can replace the Hadamard code by a shorter
mother code and still obtain a punctured code with the excellent combinatorial
properties of an RLC. In Theorem A, below, we give this question a strong
positive answer.

Of the many special properties of a Hadamard code, the property crucial for
that code’s excellent performance as a mother code turns out be its optimal
bias. Focusing for simplicity on the case $q=2$, the bias of a binary code
$\mathcal{D}$ of length $m$ is defined as

$\max\left\\{\frac{\left|\textsf{number of ones in }x-\textsf{number of zeros
in }x\right|}{m}\mid
x\in\mathcal{D}\setminus\left\\{0\right\\}\right\\}\enspace.$

The bias of a Hadamard code is the smallest possible, namely, zero. The
following informal result can thus be seen as an extension of the statement “A
random puncturing of a Hadamard code is an RLC”.

######  Theorem A (Main result about puncturing of low-bias codes (informal
version of Theorem 1)).

Let $\mathcal{D}$ be a linear333The linearity of $\mathcal{D}$ is crucial
here. Indeed, there exists a (non-linear) code $\mathcal{D}$ of small bias
such that a random puncturing of $\mathcal{D}$ is unlikely to be similar, in
the sense of Theorem A, to either an RLC or to a plain random code. For
example, one can take any low-bias code
$\mathcal{D}\subseteq{\mathbb{F}}_{2}^{m}$ that contains two codewords $x$ and
$y$, each of which has weight $\frac{m}{2}$, such that $x+y$ is the all-ones
vector. code with small bias and let $\mathcal{C}$ be a random puncturing of
$\mathcal{D}$. Then, $\mathcal{C}$ is likely to have any monotone-decreasing
local property that is typically satisfied by an RLC of similar rate.

Theorem B, below, gives broad conditions under which the hypothesis of Theorem
A can be further relaxed, from requiring low bias to just large distance of
the mother code $\mathcal{D}$.

Informally, a code property $\mathcal{P}$ is monotone-decreasing and local if,
whenever a code $\mathcal{C}$ does not satisfy $\mathcal{P}$, there exists a
small _“bad set”_ of codewords in $\mathcal{C}$ that bears witness to this
fact. By monotone-decreasing we mean that adding codewords to the code can
only make the property harder to satisfy. A code that has the same monotone-
decreasing local properties as an RLC is said to be locally similar to an RLC.
Local properties of codes were originally introduced in [MRRSW20], with the
motivation of studying the list-decodability of Gallager’s LDPC codes. We turn
to explain this connection.

List-decodability. In the model of list-decoding, the goal is to decode beyond
the unique-decoding radius. A code is said to be (combinatorially) list-
decodable up to radius $\rho$ ($0<\rho<1-\frac{1}{q}$) if every Hamming ball
of radius $\rho n$ in ${\mathbb{F}}_{q}^{n}$ has intersection of size at most
$L$ (where $L$ is small, say constant in $n$) with the code. Being list-
decodable is a monotone-decreasing local property. Indeed, to show that a code
is _not_ list-decodable, it suffices to point to a set of $L+1$ codewords that
all reside within the same radius $\rho$ Hamming ball. A list-decodable code,
when accompanied by a decoding algorithm, will allow the correction of a
$\rho$ fraction of errors up to some bounded ambiguity in the worst-case. We
refer the reader to [Gur06] for a detailed discussion of the motivation,
usefulness, and potential of the list-decoding model.

The list-decodability of RLCs has been extensively studied in previous works
ZyablovP81,GHK,CGV13,Wootters13,RW14RLC,RW18RLC,LiWootters,GLMRSW. The paper
[ZP81] already establishes that RLCs are list-decodable up to capacity.
Namely, for any fixed $R$ and $\rho$ satisfying $R<1-h_{q}(\rho)$, an 444The
$q$-ary entropy function $h_{q}$ is formally defined in Section 4.5 RLC of
rate $R$ is almost surely list-decodable up to radius $\rho$ with constant
list-size $L=L(R,\rho,q)$. The focus of the later works is pinpointing the
exact dependence of the list-size $L$ on the other parameters.

Since list-decodability is a monotone-decreasing local property, the
aforementioned results about list-deocdability of an RLC also apply to any
code that is locally similar to an RLC. Therefore, Theorem A yields a powerful
reduction, allowing us to apply these results about RLCs to the punctured code
$\mathcal{C}$. Moreover, any positive RLC list-decoding bound discovered in
the future would also immediately apply to $\mathcal{C}$. The latter may be
relevant since there are still some gaps in our knowledge of RLC list-
decodability, especially in the low-rate non-binary regime.

In addition to list-decodability, Theorem A also applies to other local
properties, such as list-recoverability, and its special case, the perfect
hashing property. Hence, Theorem A immediately yields a positive result (see
Section 6.3) about the list-recoverability of $\mathcal{C}$, via reduction to
established results about the list-recoverability of an RLC.

Theorem A and RLC derandomization. Perhaps more importantly than its
specialization to any concrete local property, Theorem A is a statement about
the robustness of the mechanism by which an RLC is generated: The theorem says
that it is possible to choose a code $\mathcal{D}$ that is radically different
from a Hadamard code, randomly puncture it, and end up with a code that, in a
local view, has the same desirable properties as an RLC.

Theorem A allows us great flexibility in choosing the mother code
$\mathcal{D}$. While the only structural property of an RLC is its linearity,
the punctured code $\mathcal{C}$ of Theorem A can be made to have additional
structure via certain choices of the mother code. For example, $\mathcal{D}$
can be taken to be a dual-BCH code, namely, a code in which every codeword
encodes a low-degree polynomial over ${\mathbb{F}}_{2^{\ell}}$
($\ell\in\mathbb{N}$) by the trace of its evaluations over
${\mathbb{F}}_{2^{\ell}}$. In a random puncturing $\mathcal{C}$ of
$\mathcal{D}$, the codewords correspond to evaluations over a random subset of
${\mathbb{F}}_{2^{\ell}}$. It is well-known (see [GR11]) that dual-BCH codes
have small bias, so Theorem A applies. Hence, this code $\mathcal{C}$ enjoys
both an algebraic structure and local similarity to an RLC.

Enforcing a structure on $\mathcal{C}$ has potential algorithmic advantages.
For example, recall that the local similarity of $\mathcal{C}$ to an RLC only
guarantees with high probability the combinatorial property of list-
decodability, but not the existence of an efficient list-decoding algorithm
for $\mathcal{C}$. Indeed, for the RLC ensemble itself, it is very likely that
no efficient list-decoding algorithm exists for any constant radius $\rho$.
Hopefully, by choosing a suitable structure for $\mathcal{C}$, one may be
obtain a code which is not only combinatorially list-decodable up to capacity,
but also amenable to efficient list-decoding algorithms.

Another application of Theorem A is a direct derandomization of RLCs.
Utilizing constructions such as [ABNNR92, Ta-17], $\mathcal{D}$ can be taken
to be an explicit low-bias linear code of length $O(n)$ (where $n$ is the
desired length of $\mathcal{C}$). With such a short mother code, only $O(n)$
random bits are needed to construct the punctured code $\mathcal{C}$, which is
locally similar to an RLC. This is in contrast to the $O(n^{2})$ random bits
needed to construct an actual RLC of the same length. While methods to sample
linear codes with $O(n)$ randomness were known in some settings, the approach
and analysis was tailored to the specific setting (e.g, via random Toeplitz
matrices for the Gilbert-Varshamov trade-off). In contrast, our approach
applies uniformly for all local properties. For list-decoding, this gives the
first linear randomness method to sample codes that achieve the trade-offs of
RLCs.

The idea of relating the local properties of a more structured code
$\mathcal{C}$ to those of an RLC already figures prominently in the previously
mentioned [MRRSW20], where a _Gallager LDPC Code_ is cast in the role of
$\mathcal{C}$. While our methods in the present work are very different, our
proof of Theorem A does use the framework of [MRRSW20], as well as the _RLC
Threshold Theorem_ [MRRSW20, Thm. 2.8] proven there.

Replacing low bias by large distance. A linear code of low bias necessarily
has large minimal distance. For example, in the binary case, the normalized
Hamming weight of a codeword $x\in\mathcal{D}\setminus\\{0\\}$ is at least
$\frac{1-\mathrm{bias}(\mathcal{D})}{2}$. Theorem B extends Theorem A by
considering the case in which the mother code $\mathcal{D}$ has large minimal
distance, but not necessarily low bias. For large enough alphabet size $q$,
large minimal distance of $\mathcal{D}$ is enough to guarantee the conclusion
of Theorem A. For small $q$, while we do not have such a general result, we
are able to use specific characteristics of the the property of list-
decodability to prove that $\mathcal{C}$ is, with high probability, list-
decodable up to capacity.

######  Theorem B (Main result about puncturing of large-distance codes
(informal version of Theorems 4 and 5)).

Let $\mathcal{D}$ be a linear code whose minimal distance is near
$1-\frac{1}{q}$, and let $\mathcal{C}$ be a random puncturing of $\mathcal{D}$
of rate $R$. Then:

  1. 1.

Let $\mathcal{P}$ be a monotone-decreasing local property that is likely
satisfied by an $RLC$ of rate $R-2\log_{q}2$. Then, $\mathcal{C}$ is likely to
satisfy $\mathcal{P}$.

  2. 2.

Even if its alphabet size is small, $\mathcal{C}$ is likely to be list-
decodable and list-recoverable up to capacity (similarly to an RLC of rate
$R$).

Achieving Shannon capacity with punctured codes. Theorems A and B are most
relevant when considering the performance of $\mathcal{C}$ as an error
correcting code in the _worst-case error_ model. To complete the picture, we
also prove the following result, dealing with the _random error_ model. It is
well-known that RLCs achieve capacity with regard to any memoryless additive
noise channel. The following informal theorem generalizes this statement to
our punctured code $\mathcal{C}$.

######  Theorem C (Puncturing of large-distance codes in stochastic channels
(informal version of Theorem 6)).

Let $\mathcal{D}$ be a linear code whose minimal distance is near
$1-\frac{1}{q}$, and let $\mathcal{C}$ be a random puncturing of $\mathcal{D}$
with rate $R$. Let $\mathcal{N}$ be a memoryless additive noise channel with
capacity at least $R+\varepsilon$. Then, it is possible to reliably
communicate across $\mathcal{N}$ using $\mathcal{C}$.

###  1.1 Previous work

Randomly punctured codes have recently gotten a lot of attention, motivated by
the study of Reed-Solomon (RS) codes [RW14, ST20, GLSTW20, FKS20, GST21]. The
RS code of dimension $1\leq k\leq q$ over the set $S\subseteq{\mathbb{F}}_{q}$
is defined as

$\mathrm{RS}_{{\mathbb{F}}_{q}}\left(S;k\right)=\left\\{\left(f(\alpha_{1}),\dots,f(\alpha_{n})\right)\mid
f\in{\mathbb{F}}_{q}[x],\ \deg(f)<k\right\\}\enspace.$

The length of the code is $n=|S|$. A classical algorithm [GS99] can
efficiently list-decode an RS code up to the Johnson radius $1-\sqrt{R}-o(1)$.

An important open question is whether efficient list-decoding of some RS codes
is possible all the way up to the capacity radius $1-R-o(1)$. A necessary
condition for such an algorithmic result is to have RS codes which are
_combinatorially_ list-decodable up to capacity, and such codes are yet
unknown. In fact, even the existence of RS codes that are combinatorially
decodable beyond the Johnson bound was only recently proven [ST20].

Our freedom in constructing an RS code lies mainly in the choice of the
evaluation set $S$. A natural choice is to take $S$ to be a uniformly random
subset of ${\mathbb{F}}_{q}$ of the desired size $n$. When $S$ is sampled this
way, the code $\mathrm{RS}_{{\mathbb{F}}_{q}}\left(S;k\right)$ is essentially
a random puncturing of the full RS code
$\mathrm{RS}_{{\mathbb{F}}_{q}}\left({\mathbb{F}}_{q};k\right)$. All of the
aforementioned works [RW14, ST20, GLSTW20, FKS20, GST21] take this viewpoint.
In particular, in [RW14, FKS20, GST21], the main results about list-
decodability of RS codes are all immediate special cases of more general
results about randomly punctured codes. Our Theorems A and B are similar in
spirit to the latter. We note that our work is the _first_ in this line to
yield punctured codes that achieve list-decoding capacity, and we do so _for
every choice of rate._ The previous works showed trade-offs that were bounded
away from list-decoding capacity for all rates.

###  1.2 On an error in a previous version of this paper regarding RS codes

The full RS code
$\mathrm{RS}_{{\mathbb{F}}_{q}}\left({\mathbb{F}}_{q};k\right)$ for small $k$
has near-optimal distance, and thus it would seem that one could apply Theorem
B to it, proving that an RS code over a random evaluation set is likely to be
locally-similar to an RLC, and, in particular, list-decodable up to capacity.
Unfortunately, the _large distance_ requirement of the theorem becomes
stricter as the alphabet $q$ grows, and impossible to achieve whenever $q$ is
larger than $n$ (see Theorem 4). An earlier version of the current paper
erroneously claimed to overcome this difficulty by passing to trace codes over
a smaller alphabet, and use it to deduce the list-decodability of certain RS
codes. Later, prompted by a question from Zeyu Guo, we have found an error in
the proof and retracted this claim.

##  2 Main Results

Before stating our main results, we formally define some of the relevant
notions.

######  Definition 2.1 (Random puncturing).

Fix some prime power $q$. Let $m,n\in\mathbb{N}$. An ($m\to n$) puncturing map
is a function $\varphi:{\mathbb{F}}_{q}^{m}\to{\mathbb{F}}_{q}^{n}$ of the
form $\varphi(u=(u_{1},\dotsc,u_{m}))=(u_{i_{1}},u_{i_{2}},\cdots,u_{i_{n}})$
for some $i_{1},\dotsc,i_{n}\in[m]$. If $i_{1},\dotsc,i_{n}$ are sampled
i.i.d. and uniformly from $[m]$, we say that $\varphi$ is a random ($m\to n$)
puncturing map.

A random $n$-puncturing of a code $\mathcal{D}\subseteq{\mathbb{F}}_{q}^{m}$
is a random code $\mathcal{C}=\varphi(\mathcal{D})=\\{\varphi(u)\mid
u\in\mathcal{D}\\}$, where
$\varphi:{\mathbb{F}}_{q}^{m}\to{\mathbb{F}}_{q}^{n}$ is a random puncturing
map. The design rate of $\mathcal{C}$ is
$\frac{\log_{q}\left|\mathcal{D}\right|}{n}$.

######  Definition 2.2.

Let $\mathcal{D}\subseteq{\mathbb{F}}_{q}^{m}$, where $q$ is a power of some
prime $p$, be a linear code and let $\eta>0$.

  1. 1.

If every $u\in\mathcal{D}\setminus\\{0\\}$ has
$\operatorname{wt}(u)\geq\frac{(q-1)(1-\eta)}{q}$, we say that $\mathcal{D}$
has $\eta$-optimal distance. Here,
$\operatorname{wt}(u)=\frac{\left|\left\\{i\in[m]\mid u_{i}\neq
0\right\\}\right|}{m}$ denotes the normalized Hamming weight of
$u\in{\mathbb{F}}_{q}^{m}$.

  2. 2.

A vector $u\in{\mathbb{F}}_{q}^{m}$ is said to be $\eta$-biased if
$\left|\sum_{i=1}^{m}\omega^{\mathrm{tr}(a\cdot u_{i})}\right|\leq m\eta$ for
all $a\in{\mathbb{F}}_{q}^{*}$. Here, $\omega=e^{\frac{2\pi i}{p}}$ and
$\mathrm{tr}:{\mathbb{F}}_{q}\to{\mathbb{F}}_{p}$ is the field trace map (see
Section 4.4). The code $\mathcal{D}$ is said to be $\eta$-biased if every
$u\in\mathcal{D}\setminus\\{0\\}$ is $\eta$-biased.

As shown in Lemma 4.13, an $\eta$-biased code also has $\eta$-optimal
distance, so the former is a stronger notion. For intuition, note that in the
binary case $\eta$-bias implies
$\frac{1-\eta}{2}\leq\operatorname{wt}(u)\leq\frac{1+\eta}{2}$ for any
$u\in\mathcal{D}\setminus\\{0\\}$, whereas $\eta$-optimal distance only
implies the lower bound on $\operatorname{wt}(u)$.

It may be simpler for the reader to focus on the case where $q$ is a prime,
i.e., $q=p$. In this case, $\mathrm{tr}$ is merely the identity map.

If $\mathcal{C}$ is a random $n$-puncturing of a code $\mathcal{D}$, the rate
of $\mathcal{C}$ is clearly bounded from above by its design rate. The
following lemma shows that when $\mathcal{D}$ is of almost optimal distance,
these two terms are very likely to coincide. In light of this lemma, we blur
the distinction between design rate and actual rate.

######  Lemma 2.3 (Actual rate equals design rate whp).

Let $\mathcal{D}\subseteq{\mathbb{F}}_{q}^{m}$ be a linear code of
$\eta$-optimal distance, and let $\mathcal{C}$ be a length-$n$ random
puncturing of $\mathcal{D}$, of design rate $R\leq 1-\log_{q}(1+\eta
q)-\varepsilon$. Then, with probability at least $1-q^{-n\varepsilon}$, the
rate of $\mathcal{C}$ is equal to its design rate.

###### Proof.

The rate of $\mathcal{C}$ is smaller than $R$ if and only if there exists a
non-zero word $u\in\mathcal{D}$ such that only coordinates $i\in[m]$ for which
$u_{i}=0$ are sampled for inclusion in $\mathcal{C}$. For a given $u$, this
happens with probability

$(1-\operatorname{wt}(u))^{n}\leq\left(\frac{1}{q}+\frac{q-1}{q}\eta\right)^{n}\leq\left(\frac{1}{q}+\eta\right)^{n}=q^{-n(1-\log(1+q\eta))}\
.$

The claim follows by a union bound over the non-zero words of $\mathcal{D}$,
of which there are $q^{Rn}-1$, and the assumed upper bound on $R$. ∎

######  Definition 2.4 (clustered sets and list-decodability).

Fix $\rho\in[0,1]$. A set of vectors $W\subseteq{\mathbb{F}}_{q}^{n}$ is
called $\rho$-clustered if there exists some $z\in{\mathbb{F}}_{q}^{n}$ such
that $\operatorname{wt}(u-z)\leq\rho$ for each $u\in W$. A code
$\mathcal{C}\subseteq{\mathbb{F}}_{q}^{n}$ is said to be $(\rho,L)$-list-
decodable if it does not contain any $\rho$-clustered set of codewords of size
$L+1$.

###  2.1 A framework for studying properties of codes

In order to formulate our results, we need to recall some of the framework for
studying _local and row-symmetric properties of linear 555This framework makes
sense for linear as well as non-linear codes. In this work we restrict
ourselves to the linear case. codes_, established in [MRRSW20, GMRSW21].666The
notion of a _local property_ from [MRRSW20] was later refined and split into
two parts in [GMRSW21], where it appears as a _row-symmetric_ and _local_
property. We follow the latter convention.

A property $\mathcal{P}$ of length-$n$ linear codes over ${\mathbb{F}}_{q}$ is
a collection of linear codes in ${\mathbb{F}}_{q}^{n}$. A linear code
$\mathcal{C}\subseteq{\mathbb{F}}_{q}^{n}$ such that
$\mathcal{C}\in\mathcal{P}$ is said to satisfy $\mathcal{P}$. If $\mathcal{P}$
is upwards closed with regard to containment, it is said to be monotone-
increasing.777While Section 1 discussed monotone-decreasing properties, it
will henceforth be more convenient to deal with monotone-increasing
properties. Note that the negation of a monotone-decreasing property is
monotone-increasing. Hence, the statement “the code $\mathcal{C}$ satisfies
every monotone-decreasing local property typically satisfied by an RLC” is
equivalent to “every monotone-increasing local property typically _not_
satisfied by an RLC is also _not_ satisfied by $\mathcal{C}$.

######  Definition 2.5 (Local and row-symmetric properties).

Let $\mathcal{P}$ be a monotone-increasing property of linear codes in
${\mathbb{F}}_{q}^{n}$. We define the following notions.

  1. 1.

Fix $b\in\mathbb{N}$. Suppose that there exists a family
$\mathcal{B}_{\mathcal{P}}$ of sets of words, such that every
$B\in\mathcal{B}_{\mathcal{P}}$ is a subset of ${\mathbb{F}}_{q}^{n}$ with
$|B|\leq b$, and such that

$\mathcal{C}\text{ satisfies }\mathcal{P}\quad\iff\quad\exists
B\in\mathcal{B}_{\mathcal{P}}~{}~{}B\subseteq\mathcal{C}\enspace.$

Then, we say that $\mathcal{P}$ is a $b$-local property.

  2. 2.

Suppose that, whenever a code $\mathcal{C}\subseteq{\mathbb{F}}_{q}^{n}$
satisfies $\mathcal{P}$ and $\pi$ is a permutation on
$\left\\{1,\dotsc,n\right\\}$, the code $\left\\{\pi x\mid
x\in\mathcal{C}\right\\}$ also satisfies $\mathcal{P}$. We then say that
$\mathcal{P}$ is row-symmetric888The reason for this terminology will be made
clear in Observation 6.2.. Here, $\pi x$ is the vector obtained by permuting
the coordinates of $x$ according to $\pi$.

The following is immediate from the definition of $(\rho,L)$-list-
decodability.

######  Observation 2.6.

Let $q$ be a prime power and $n\in\mathbb{N}$. Fix $\rho\in(0,1)$,
$L\in\mathbb{N}$, and let $\mathcal{P}$ be the monotone-increasing property
consisting of codes in ${\mathbb{F}}_{q}^{n}$ that are not
$\left(\rho,L\right)\text{-list-decodable}$. Then, $\mathcal{P}$ is
$(L+1)$-local and row-symmetric.

Let $\mathcal{P}$ be a monotone-increasing property over
${\mathbb{F}}_{q}^{n}$. Suppose that $\mathcal{P}$ is nonempty, namely, that
it is satisfied by the complete code ${\mathbb{F}}_{q}^{n}$. We denote its
threshold by

${\mathrm{RLC}}(\mathcal{P})=\min\left\\{R\in[0,1]\mid\mathrm{Pr}\left[C_{\mathrm{RLC}}^{n,q}(R)\text{
satisfies }\mathcal{P}\right]\geq\frac{1}{2}\right\\}\enspace,$

where $C_{\mathrm{RLC}}^{n,q}(R)$ is a random linear code of rate $R$ in
${\mathbb{F}}_{q}^{n}$.

This terminology is motivated by the following theorem, which states that the
probability of an RLC of rate $R$ satisfying a local, row-symmetric and
monotone-increasing property $\mathcal{P}$, as a function of $R$, rapidly
climbs near the threshold from $o(1)$ to $1-o(1)$.

######  Theorem 2.7 (Thresholds for local and row-symmetric properties
[MRRSW20, Thm. 2.8]).

999The theorem as stated in [MRRSW20] deals only with the regime of constant
$q$ and $b$. The current statement, which allows $q$ and $b$ to depend on $n$,
follows by inspecting the proof in [MRRSW20].

Let $\mathcal{P}\subseteq{\mathbb{F}}_{q}^{n}$ be a random linear code of
radius $R$ and Let $\mathcal{P}$ be a monotone-increasing, $b$-local and row-
symmetric property over ${\mathbb{F}}_{q}^{n}$, where
$\frac{n}{\log_{q}n}\geq\omega_{n\to\infty}\left(q^{2b}\right)$. The following
now holds for every $\varepsilon>0$.

  1. 1.

If $R\leq{\mathrm{RLC}}(\mathcal{P})-\varepsilon$ then

$\mathrm{Pr}\left[\mathcal{C}\text{ satisfies }\mathcal{P}\right]\leq
q^{-(\varepsilon-o_{n\to\infty}(1))n}\enspace.$

  2. 2.

If $R\geq{\mathrm{RLC}}(\mathcal{P})+\varepsilon$ then

$\mathrm{Pr}\left[\mathcal{C}\text{ satisfies }\mathcal{P}\right]\geq
1-q^{-(\varepsilon-o_{n\to\infty}(1))n}\enspace.$

###  2.2 Theorem A: Randomly punctured low-bias codes

Theorem 1, below, is a formal statement of Theorem A.

######  Theorem 1 (Puncturings of low-bias linear codes are locally similar to
random linear codes).

Let $q$ be a prime power, and let $\mathcal{P}$ be a monotone-increasing, row-
symmetric and $b$-local property over ${\mathbb{F}}_{q}^{n}$, where
$\frac{n}{\log n}\geq\omega_{n\to\infty}\left(q^{2b}\right)$. Let
$\mathcal{D}\subseteq{\mathbb{F}}_{q}^{m}$ be a linear code. Let $\mathcal{C}$
be a random $n$-puncturing of $\mathcal{D}$ of design rate
$R\leq{\mathrm{RLC}}(\mathcal{P})-\varepsilon$ for some $\varepsilon>0$.
Suppose that $\mathcal{D}$ is $\left(\frac{\varepsilon b\ln
q}{q^{b}}\right)$-biased. Then,

$\mathrm{Pr}\left[\mathcal{C}\text{ satisfies }\mathcal{P}\right]\leq
q^{-(\varepsilon-o_{n\to\infty}(1))n}\enspace.$

###  2.3 Applications of Theorem 1 for list-decodability

In our discussion of list-decoding capacity in Section 1 we treated the rate
$R$ as fixed, and the list-decoding capacity radius $\rho$ as a function of
$R$ and the field size. Henceforth we will prefer to think of $R$ as depending
on some fixed $\rho$.

The _List-Decoding Capacity Theorem_ [GRS, Thm. 7.4.1] states that the
_optimal rate_ for radius $\rho$ list-decoding over the field
${\mathbb{F}}_{q}$ is $R^{*}=1-h_{q}(\rho)$, where

$h_{q}(\rho)=-\rho\log_{q}\rho-(1-\rho)\log_{q}(1-\rho)+\rho\log_{q}(q-1)$ (1)

is the $q$-ary entropy function (see Section 4.5). In other words, there exist
infinite families of codes of rate $R^{*}-\varepsilon$ that are list-decodable
up to radius $\rho$ with list-size independent of the block length $n$, but no
such families exist for rate $R^{*}+\varepsilon$.

As mentioned in Section 1, the list-decodability of RLCs has been extensively
studied. Positive and negative results of this sort can be stated,
respectively, as lower and upper bounds on
${\mathrm{RLC}}\left({\mathrm{LD}}_{\rho,L,q}\right)$, where
${\mathrm{LD}}_{\rho,L,q}$ is the monotone-increasing property of a code over
${\mathbb{F}}_{q}$ _not_ being $(\rho,L)$-list-decodable. For example, the
main result of [GHK11] can be stated as

${\mathrm{RLC}}\left({\mathrm{LD}}_{\rho,L,q}\right)\geq
1-h_{q}(\rho)-O_{\rho,q}\left(\frac{1}{L}\right)\enspace$ (2)

for all $\rho$, $q$ and $L$. In the binary regime, the main result of [LW21]
together with a negative result from [GLMRSW20] yield the very precise bound

$1-h_{2}(\rho)\cdot\frac{L-1}{L-2}\leq{\mathrm{RLC}}\left({\mathrm{LD}}_{\rho,L,2}\right)\leq
1-h_{2}(\rho)\frac{L+1}{L}$ (3)

for all $\rho$ and $L\geq 3$. By Observation 2.6, ${\mathrm{LD}}_{\rho,L,q}$
is $(L+1)$-local and row-symmetric, so Theorem 1 applies to it. Plugging in
Eqs. 2 and 3 yields the following corollary.

######  Corollary 2 (Puncturings of certain linear codes are locally similar
to random linear codes).

Fix a prime power $q$, $\rho\in\left(0,1-\frac{1}{q}\right)$, $L\in\mathbb{N}$
and $\varepsilon>0$. Let $\mathcal{D}\subseteq{\mathbb{F}}_{q}^{m}$ be an
$\left(\frac{\varepsilon(L+1)\ln q}{q^{L+1}}\right)$-biased linear code . Let
$\mathcal{C}$ be a random $n$-puncturing of $\mathcal{D}$ of design rate $R$,
where $\frac{n}{\log n}\geq\omega_{n\to\infty}\left(q^{2(L+1)}\right)$. Then,

  1. 1.

If $R<1-h_{q}(\rho)-\frac{C_{\rho,q}}{L}-\varepsilon$ then $\mathcal{C}$ is
$\left(\rho,L\right)\text{-list-decodable}$ with probability
$1-q^{-\left(\varepsilon-o_{n\to\infty}(1)\right)n}$. Here, $C_{\rho,q}$ is a
constant depending on $\rho$ and $q$.

  2. 2.

If $q=2$, $L\geq 3$ and $R<1-h_{2}(\rho)\cdot\frac{L-1}{L-2}-\varepsilon$ then
$\mathcal{C}$ is $\left(\rho,L\right)\text{-list-decodable}$ with probability
$1-2^{-\left(\varepsilon-o_{n\to\infty}(1)\right)n}$.

Other positive results about RLC list-decodability (e.g., [Woo13]) can be
similarly used to obtain bounds on the list-decodability of randomly punctured
codes.

List-recoverability is another property of interest to which Theorem 1
applies, similarly allowing us to reduce from known results about RLCs. See
Section 6.3 for more details.

###  2.4 Derandomization of RLCs

As discussed in Section 1, Theorem 1 can be invoked to derandomize RLCs by
casting a code of short block length and low bias in the role of the mother
code $\mathcal{D}$. One result that can be achieved via this method is the
following theorem. For simplicity, we focus on the binary case.

######  Theorem 3 (Codes locally similar to an RLC with linear randomness).

There exists a randomized algorithm that, given $b\in\mathbb{N}$,
$\varepsilon>0$, $R^{*}\in[\varepsilon,1]$ and $n\in\mathbb{N}$, where
$\frac{n}{\log_{2}n}\geq\omega_{n\to\infty}\left(2^{2b}\right)$ and
$n\geq\omega_{n\to\infty}(1/\varepsilon)$, samples a generating matrix for a
linear code $\mathcal{C}\subseteq{\mathbb{F}}_{2}^{n}$ of rate
$R=R^{*}-\varepsilon$ such that

$\mathrm{Pr}\left[\mathcal{C}\text{ satisfies some property
}\mathcal{P}\in\mathcal{K}\right]\leq 2^{-\Omega(\varepsilon n)}.$ (4)

Here, $\mathcal{K}$ is the family of all monotone-increasing, $b$-local and
row-symmetric properties $\mathcal{P}$ over ${\mathbb{F}}_{2}^{n}$ for which
the threshold $~{}{\mathrm{RLC}}(\mathcal{P})$ is at least $R^{*}$. This
algorithm uses $O\left(n\left(b+\log_{2}\frac{1}{\varepsilon}\right)\right)$
random bits, and works in time polynomial in $n$.

###  2.5 Theorem B: Randomly punctured codes of near-optimal distance

Theorems 4 and 5 are detailed version of, respectively, the two parts of
Theorem B. These theorems extend Theorem 1, in certain scenarios, to the case
where the mother code $\mathcal{D}$ has near-optimal distance but not
necessarily low bias. Theorem 4 states that the conclusion of Theorem 1 is
still valid, provided that the alphabet $q$ is large enough, and the property
$\mathcal{P}$ is scalar-invariant—a new definition given here.

######  Definition 2.8 (Scalar invariant property).

Let $\mathcal{P}$ be a property of codes in ${\mathbb{F}}_{q}^{n}$. Suppose
that, for every code $\mathcal{C}$ satisfying $\mathcal{P}$ and for every
diagonal full-rank matrix $\Lambda\in{\mathbb{F}}_{q}^{n\times n}$, the code
$\Lambda\mathcal{C}:=\left\\{\Lambda u\mid u\in\mathcal{C}\right\\}$ also
satisfies $\mathcal{P}$. Then, $\mathcal{P}$ is said to be scalar-invariant.

It is not hard to see that $(\rho,L$)-list-decodability (as well as its
negation, the property of _not_ being $\left(\rho,L\right)\text{-list-
decodable}$) is a scalar-invariant property for all $\rho$ and $L$. The same
holds for list-recoverability (see Section 6.3).

######  Theorem 4 (Puncturings of near-optimal distance linear codes with
large alphabet are locally similar to random linear codes).

Let $q$ be a prime power, and let $\mathcal{P}$ be a monotone-increasing, row-
symmetric, $b$-local and scalar-invariant property over
${\mathbb{F}}_{q}^{n}$, where $\frac{n}{\log
n}\geq\omega_{n\to\infty}\left(q^{2b}\right)$. Let
$\mathcal{D}\subseteq{\mathbb{F}}_{q}^{m}$ be a linear code of
$q^{-b}$-optimal distance. Let $\mathcal{C}$ be a random $n$-puncturing of
$\mathcal{D}$ of design rate
$R\leq{\mathrm{RLC}}(\mathcal{P})-\varepsilon-2\log_{q}2$ for some
$\varepsilon>0$. Then,

$\mathrm{Pr}\left[\mathcal{C}\text{ satisfies }\mathcal{P}\right]\leq
q^{-(\varepsilon-o_{n\to\infty}(1))n}\enspace.$

Theorem 5 deals specifically with list-decodability rather than a general code
property. The theorem exploits certain characteristics of the proof of [GHK11]
(see Eq. 2), and shows that this specific result about list-decodability of
RLCs can be applied to our randomly-punctured code $\mathcal{C}$ as long as
the mother code has near-optimal distance, regardless of the alphabet size.
The relevant characteristics of [GHK11] are discussed in Remark 6.14.

######  Theorem 5 (A puncturing of a near-optimal distance code is whp list-
decodable up to capacity).

Fix a prime power $q$. Let $L,n\in\mathbb{N}$ and $0<\rho<\frac{q-1}{q}$, such
that $\frac{n}{\log_{q}n}\geq\omega_{n\to\infty}\left(q^{L+1}\right)$. Let
$\mathcal{D}\subseteq{\mathbb{F}}_{q}^{m}$ be a linear code with
$\eta$-optimal distance, where $\eta=q^{-L+1}$. Let $\mathcal{C}$ be a random
$n$-puncturing of $\mathcal{D}$ of design rate $R$, where $R\leq
1-h_{q}(\rho)-\frac{K}{L}$ for some constant $K=K_{\rho,q}$. Then,

$\mathrm{Pr}\left[\mathcal{C}\text{ is }\left(\rho,L\right)\text{-list-
decodable}\right]\geq 1-q^{-\Omega(n)}\enspace.$

Furthermore, one can take

$K_{\rho,q}\leq\mathrm{exp}\left(O\left(\frac{(\log
q)^{2}}{\min\left\\{(1-1/q-\rho)^{2},\rho\right\\}}\right)\right)$ (5)

and, in particular, $K_{\rho,q}\leq\mathrm{poly}(q)$ whenever $\rho$ is
bounded away from $0$ and $1-\frac{1}{q}$.

###  2.6 Theorem C: Randomly punctured codes in the stochastic error model

######  Definition 2.9 (Additive noise channel).

Let $\nu$ be a distribution over ${\mathbb{F}}_{q}$. The $\nu$-memoryless
additive noise channel with distribution $\nu$ takes as input a vector
$x\in{\mathbb{F}}_{q}^{n}$ and outputs the vector $x+z$, where
$z\in{\mathbb{F}}_{q}^{n}$ has entries independently sampled from $\nu$.

For $z\in{\mathbb{F}}_{q}^{n}$, we write $\nu(z)=\prod_{i=1}^{n}\nu(z_{i})$
for the probability of $z$ under the product distribution $\nu^{n}$.

The capacity of the $\nu$-memoryless additive noise channel is $1-H_{q}(\nu)$.
Here, $H_{q}(\nu)$ is the base-$q$ entropy

$H_{q}(\nu)=-\sum_{x\in\mathrm{supp}(\nu)}\nu(x)\log_{q}\nu(x)\enspace.$

The maximum likelihood decoder under uniform prior (MLDU) for a code
$\mathcal{C}\subseteq{\mathbb{F}}_{q}^{n}$ with regard to the $\nu$-memoryless
additive noise channel receives a word $y\in{\mathbb{F}}_{q}^{n}$ and returns
a codeword $x\in\mathcal{C}$ for which $\nu(y-x)$ is maximal. In other words,
$x$ maximizes the likelihood of the channel outputting $y$ given input $x$.

It is well-known that an RLC with MLDU decoding achieves capacity with regard
to any memoryless additive noise channel. Theorem C, stated here formally as
Theorem 6, generalizes this fact to random puncturings of low-bias codes.

######  Theorem 6 (A puncturing of a low-bias code achieves capacity with
regard to memoryless additive noise).

Fix a prime power $q$, a distribution $\nu$ over ${\mathbb{F}}_{q}$ and
$0<\varepsilon<1$. Let $\mathcal{D}\subseteq{\mathbb{F}}_{q}^{m}$ be an
$\frac{\varepsilon}{3(q-1)}$-biased linear code. Let $\mathcal{C}$ be a random
$n$-puncturing of $\mathcal{D}$ of design rate $R\leq
1-H_{q}(\nu)-\varepsilon$. Then, with probability
$1-q^{-\Omega_{\nu}\left(\varepsilon n\right)}$, it holds for all
$x\in\mathcal{C}$ that

$\Pr_{z\sim\nu^{n}}\left[\textnormal{the MLDU outputs $x$ on input
$x+z$}\right]\geq 1-2q^{-c_{\nu}\varepsilon^{2}n}\enspace,$ (6)

for some $c_{\nu}>0$ that depends only on $\nu$.

We note that the code property of being _decodable with regard to the
$\nu$-memoryless additive noise channel_, where $\nu$ is a generic
distribution, is not local in the sense of Definition 2.5. Consequently,
Theorem 6 is proven by more direct means, and not as a consequence of the
framework described in Section 2.1. It is an interesting question whether this
framework can be extended to also apply to properties such as decodability and
list-decodability in stochastic settings.

###  2.7 Organization

The rest of the paper is organized as follows. In Section 3 we survey our
techniques by sketching a proof for a weaker version of Corollary 2. Section 4
establishes some general definitions and lemmas used in the main proofs. In
Section 5 we prove Theorem 5 about list-decodability of randomly punctured
codes, based on the result of [GHK11]. In Section 6 we give more details on
the code property framework, and prove Theorems 1 and 4 about punctured codes
that are locally-similar to an RLC. In Section 7 we prove Theorem 3, dealing
with derandomization of RLCs. Finally, Theorem 6 about punctured codes in the
stochastic error model is proved in Section 8.

##  3 Technical overview

For the sake of exposition, we begin by proving Theorem 7—a weaker version of
Corollary 2. Theorem 7 showcases the techniques by which we prove our main
results in a simplified setting. Rather than reducing from state of the art
results about RLC list-decodability, Theorem 7 is proven directly, resulting
in worse bounds on the list-size. For simplicity, we restrict ourselves to the
binary regime.

######  Theorem 7.

Let $\rho\in\left(0,\frac{1}{2}\right)$ and $L\in\mathbb{N}$. Then, there
exist $\eta(L)>0$ and $\varepsilon(L)>0$ with
$\varepsilon(L)\xrightarrow[L\to\infty]{}0$, such that the following holds.
Let $\mathcal{D}\subseteq{\mathbb{F}}_{2}^{m}$ be a linear $\eta$-biased code,
and let $\mathcal{C}$ be a random $n$-puncturing of $\mathcal{D}$ of design
rate $R\leq 1-h_{2}(\rho)-\varepsilon$. Then $\mathcal{C}$ is
$\left(\rho,L\right)\text{-list-decodable}$ with high probability as
$n\to\infty$.

###### Proof sketch.

Let $\varphi:{\mathbb{F}}_{2}^{m}\to{\mathbb{F}}_{2}^{n}$ be the random
puncturing map by which $\mathcal{C}$ is generated from $\mathcal{D}$. Write
$b=\lceil\log_{2}(L+1)\rceil$. Now any set of $L+1$ vectors in
${\mathbb{F}}_{2}^{n}$ must contain a subset of $b$ linearly-independent
vectors. In particular, for $\mathcal{C}$ to contain a $\rho$-clustered set of
size $L+1$, it must contain a $\rho$-clustered set of $b$ linearly-independent
vectors (this argument originated in [ZP81]). Thus, the probability, taken
over the random puncturing $\varphi$, that $\mathcal{C}\text{ is
}\textbf{not}\left(\rho,L\right)\text{-list-decodable}$ is at most

$\displaystyle\mathrm{Pr}\left[\exists v_{1},\dotsc,v_{b}\in\mathcal{C}\text{
which are }\rho\text{-clustered and linearly-independent}\right]$
$\displaystyle=\mathrm{Pr}\left[\exists u_{1},\dotsc,u_{b}\in\mathcal{D}\text{
s.t.\ }\varphi(u_{1}),\dotsc,\varphi(u_{b})\text{ are }\rho\text{-clustered
and linearly-independent}\right]$ $\displaystyle\leq\mathrm{Pr}\left[\exists
u_{1},\dotsc,u_{b}\in\mathcal{D}\text{ which are linearly independent, s.t.\
}\varphi(u_{1}),\dotsc,\varphi(u_{b})\text{ are }\rho\text{-clustered}\right]$
$\displaystyle\leq\sum_{\begin{subarray}{c}u_{1},\dotsc u_{b}\in\mathcal{D}\\\
\text{linearly
independent}\end{subarray}}\mathrm{Pr}\left[\varphi(u_{1}),\dotsc,\varphi(u_{b})\text{
are $\rho$-clustered}\right]\enspace,$

where the penultimate inequality is because linear-independence of
$u_{1},\dotsc,u_{b}$ is a necessary condition for linear-independence of
$\varphi(u_{1}),\dotsc,\varphi(u_{b})$. The sum on the right hand side has at
most $\left|\mathcal{D}\right|^{b}=2^{bRn}$ terms, so it suffices to show that

$\mathrm{Pr}\left[\varphi(u_{1}),\dotsc,\varphi(u_{b})\text{ are
$\rho$-clustered}\right]\leq 2^{-bRn-\omega(1)}$ (7)

whenever $u_{1},\dotsc,u_{b}\in\mathcal{D}$ are linearly independent.

Let $B\in{\mathbb{F}}_{2}^{m\times b}$ be the matrix whose columns are
$u_{1},\dotsc,u_{b}$, and let $\sigma$ denote the distribution, over
${\mathbb{F}}_{2}^{b}$, of a uniformly random row of $B$. Let
$A\in{\mathbb{F}}_{2}^{n\times b}$ be the matrix whose columns are
$\varphi(u_{1}),\dotsc,\varphi(u_{b})$. A crucial observation is that $A$ is a
random matrix whose rows are sampled independently from $\sigma$. At this
point, if $\sigma$ were the uniform distribution over ${\mathbb{F}}_{2}^{b}$,
we would be done. Indeed, $\sigma$ being uniform means that the columns of
$A$, call them $c_{1},c_{2},\dots,c_{b}$, are sampled independently and
uniformly from ${\mathbb{F}}_{2}^{n}$. This establishes Eq. 7 since

$\displaystyle\Pr_{c_{1},\dotsc,c_{b}\sim\mathsf{U}({\mathbb{F}}_{2}^{n})}\left[c_{1},\dotsc,c_{b}\text{
are $\rho$-clustered}\right]$
$\displaystyle\leq\sum_{z\in{\mathbb{F}}_{2}^{n}}\sum_{y_{1},\dots,y_{b}\in
B(z,\rho
n)}\Pr_{c_{1},\dotsc,c_{b}\sim\mathsf{U}({\mathbb{F}}_{2}^{n})}\left[\bigwedge_{i=1}^{b}(c_{i}=y_{i})\right]$
$\displaystyle=\sum_{z\in{\mathbb{F}}_{2}^{n}}\sum_{y_{1},\dots,y_{b}\in
B(z,\rho n)}(2^{-b})^{n}$ (8)
$\displaystyle\leq\sum_{z\in{\mathbb{F}}_{2}^{n}}2^{bh_{2}(\rho)n}(2^{-b})^{n}=2^{n\left(bh_{2}(\rho)-b+1\right)}$
$\displaystyle\leq 2^{-bRn-n}\enspace,$ (9)

where $B(z,\rho n)$ denotes the Hamming ball of radius $\rho n$ around $z$,
and the last inequality Eq. 9 holds for, say, $\varepsilon=\frac{2}{b}$. Note
that $\varepsilon\leq O\left(\frac{1}{\log L}\right)$.

We now use a certain formulation of the _Vazirani XOR-Lemma_ (see, e.g.,
[Gol11]) to show that $\sigma$ is in fact arbitrarily close to the uniform
distribution over ${\mathbb{F}}_{2}^{b}$. This allows us to finish the theorem
by extending the above argument from uniform $\sigma$ to almost-uniform
$\sigma$.

######  Lemma 3.1 (Vazirani XOR-Lemma).

Let $\sigma$ be a distribution over ${\mathbb{F}}_{2}^{b}$ such that for every
$y\in{\mathbb{F}}_{q}^{b}\setminus\\{0\\}$, we have
$\tfrac{1-\eta}{2}\leq\Pr_{x\sim\sigma}\left[\left\langle
x,y\right\rangle=1\right]\leq\tfrac{1+\eta}{2}$. Then, $\sigma$ is
$\left(2^{b}\cdot\eta\right)$-close in _total-variation distance_ to the
uniform distribution over ${\mathbb{F}}_{2}^{b}$.

In our case, $\Pr_{x\sim\sigma}\left[\left\langle
x,y\right\rangle=1\right]=\operatorname{wt}(By)$. Since the columns of $B$
belong to $\mathcal{D}$ and are linearly-independent, $By$ is a non-zero
codeword of $\mathcal{D}$. Our assumption about $\mathcal{D}$ having small
bias means that $\operatorname{wt}(By)$ is very close to $\frac{1}{2}$, so the
hypothesis of Lemma 3.1 is satisfied. Thus, in the above calculation the rows
of $A$ are sampled i.i.d from a distribution $\sigma\sim{\mathbb{F}}_{2}^{b}$
which has statistical distance at most $2^{b}\eta$ from uniform. Therefore, we
can replace the $2^{-b}$ term in Eq. 8 by an upper bound $(2^{-b}+2^{b}\eta)$.
By taking $\eta$ small enough, say at most $2^{-2b}$, the bound in Eq. 9
remains valid by slightly adjusting parameters (e.g., taking
$\varepsilon=\tfrac{3}{b}$). ∎

##  4 Preliminaries

###  4.1 General notation

We denote the uniform distribution over a finite nonempty set $S$ by
$\mathsf{U}(S)$.

For $a,b\in{\mathbb{R}}$, we denote $\mathrm{exp}_{a}\left(b\right)=a^{b}$.

The constants implied by asymptotic notation are universal unless stated
otherwise. To indicate that the hidden constant may depend on, e.g., for the
parameter $p$, we write “$O_{p}(\cdot)$”.

If $A\in{\mathbb{F}}_{q}^{m\times b}$ and
$\mathcal{C}\subseteq{\mathbb{F}}_{q}^{m}$, we write $A\subseteq\mathcal{C}$
to mean that each column of $A$ is a codeword in $\mathcal{C}$. Given a
puncturing map $\varphi:{\mathbb{F}}_{q}^{m}\to{\mathbb{F}}_{q}^{n}$, let
$\varphi(A)$ denote the matrix obtained from $A$ by applying $\varphi$ to each
column.

###  4.2 A characterization of list-decodable linear codes

Recall the notion of a $\rho$-clustered set (Definition 2.4.)

######  Definition 4.1.

Fix $\rho\in[0,1]$, $L\in\mathbb{N}$. A matrix $A\in{\mathbb{F}}_{q}^{n\times
b}$ ($1\leq b\leq L$) with $\operatorname{rank}A=b$ is _$(\rho,L)$ -span-
clustered_ if the column-span of $A$ contains a $\rho$-clustered set of size
$L$.

Note that for a linear code $\mathcal{C}\subseteq{\mathbb{F}}_{q}^{n}$ we have

$\mathcal{C}\text{ is \emph{not} }\left(\rho,L\right)\text{-list-
decodable}\iff\exists A\in{\mathbb{F}}_{q}^{n\times b}\text{such that $A$ is
$(\rho,L+1)$-span-clustered and }A\subseteq\mathcal{C}\enspace.$

Furthermore, we can always take $b$ to be in the range $[\log_{q}(L+1),L+1]$.
Indeed, a matrix of rank smaller than $\log_{q}(L+1)$ cannot be
$(\rho,(L+1))$-span-clustered since its span has cardinality smaller than
$L+1$. On the other hand, a rank larger than $L+1$ is never needed since,
given a $\rho$-clustered set $W\subseteq\mathcal{C}$ with $|W|=L+1$, one can
take $A$ to be a matrix whose columns are a maximal linearly independent
subset of $W$.

###  4.3 The scalar-multiplied code $\Lambda\mathcal{C}$ and scalar-expanded
code $\mathcal{D}^{*}$

Let

$\Gamma_{n}=\left\\{\Lambda\in{\mathbb{F}}_{q}^{n\times n}\mid\Lambda\text{ is
diagonal and of full-rank}\right\\}\enspace.$

Recall that, for $\Lambda\in\Gamma_{n}$ and a code
$\mathcal{C}\subseteq{\mathbb{F}}_{q}^{n}$, we denote
$\Lambda\mathcal{C}=\left\\{\Lambda u\mid u\in\mathcal{C}\right\\}$
(Definition 2.8). If $\mathcal{P}$ is a scalar-invariant property (such as
list-decodability), the question of whether a code $\mathcal{C}$ satisfies
$\mathcal{P}$ reduces to that of any code of the form $\Lambda\mathcal{C}$. To
take advantage of this reduction, we shall focus on the random code
$\Lambda\mathcal{C}$ where $\Lambda\sim\mathsf{U}(\Gamma_{n})$. If
$\mathcal{C}$ is a random puncturing of some code $\mathcal{D}$, we can
realize the code $\Lambda\mathcal{C}$ as a puncturing of the code
$\mathcal{D}^{*}$, which we now define.

######  Definition 4.2.

Given $u\in{\mathbb{F}}_{q}^{m}$, let $u^{*}\in{\mathbb{F}}_{q}^{m(q-1)}$
denote the vector

$u^{*}={{{{\odot}}}}_{a\in{\mathbb{F}}_{q}^{*}}\ (au)\enspace,$

where ${{{{\odot}}}}$ stands for concatenation of vectors. Given a matrix
$B\in{\mathbb{F}}_{q}^{m\times b}$ with columns $a_{1},\dotsc,a_{b}$, let
$B^{*}\in{\mathbb{F}}_{q}^{m(q-1)\times b}$ be the matrix whose columns are
$a_{1}^{*},\dotsc,a_{b}^{*}$. Denote $\mathcal{D}^{*}=\\{u^{*}\mid
u\in\mathcal{D}\\}\subseteq{\mathbb{F}}_{q}^{m(q-1)}$.

######  Observation 4.3.

The code $\Lambda\mathcal{C}$, where $\Lambda\sim\mathsf{U}(\Gamma_{n})$ and
$\mathcal{C}$ is a random $n$-puncturing of $\mathcal{D}$, is distributed
identically to a random $n$-puncturing of $\mathcal{D}^{*}$.

###  4.4 Fourier transform

We recall the following elementary facts about the Fourier transform101010Our
convention is to use counting norm for $f$ and expectation norm for $\hat{f}$.
of a function $f:{\mathbb{F}}_{q}^{b}\to\mathbb{C}$.

######  Definition 4.4 (Fourier (and inverse Fourier) transform).

Suppose that $q=p^{r}$ for some prime $p$, and let $\omega=e^{\frac{2\pi
i}{p}}$. Let $b\in\mathbb{N}$ and let $f:{\mathbb{F}}_{q}^{b}\to\mathbb{C}$.
Then $\widehat{f}:{\mathbb{F}}_{q}^{b}\to\mathbb{C}$ is defined by

$\widehat{f}(y)=\sum_{x\in{\mathbb{F}}_{q}^{b}}f(x)\cdot\overline{\chi_{y}(x)},\quad\text{where}\quad\chi_{y}(x)=\omega^{\mathrm{tr}\left\langle
x,y\right\rangle}\enspace.$

Here, $\mathrm{tr}:{\mathbb{F}}_{q}\to{\mathbb{F}}_{p}$ stands for the field
trace function $\mathrm{tr}(x)=\sum_{i=0}^{r-1}x^{p^{i}}$. We also have the
Fourier inversion formula:

$f(x)=q^{-b}\sum_{y\in{\mathbb{F}}_{q}^{b}}\widehat{f}(y)\chi_{y}(x)\enspace.$

######  Fact 4.5 (Parseval’s identity).

Let $f,g:{\mathbb{F}}_{q}^{b}\to\mathbb{C}$. Then,

$\sum_{x\in{\mathbb{F}}_{q}^{b}}f(x)\overline{g(x)}=\mathbb{E}_{y\sim\mathsf{U}({\mathbb{F}}_{q}^{b})}\left[\widehat{f}(y)\overline{\widehat{g}(y)}\right]\enspace.$

In particular,
$\sum_{x\in{\mathbb{F}}_{q}^{b}}\left|f(x)\right|^{2}=\mathbb{E}_{y\sim\mathsf{U}({\mathbb{F}}_{q}^{b})}\left[\left|\widehat{f}(y)\right|^{2}\right]$.

###  4.5 Entropy and KL-divergence

Given $x\in[0,1]$, we write

$h_{q}(x)=-x\log_{q}x-(1-x)\log_{q}(1-x)+x\log_{q}(q-1)$

for the base-$q$ entropy of a random variable over $\\{0,\dotsc,q-1\\}$, which
takes $0$ with probability $1-x$ and each $i\in\\{1,\dotsc,q-1\\}$ with
probability $\frac{x}{q-1}$.

The $q$-ary Kullback-Leibler Divergence of two distributions $\tau,\sigma$
over a finite set $S$ is

${D_{\mathrm{KL}}}_{q}\left(\tau\parallel\sigma\right)=\sum_{s\in
S}\tau(s)\log_{q}\frac{\tau(s)}{\sigma(s)}\enspace.$

###  4.6 The empirical distribution of the rows of a matrix

######  Definition 4.6.

Given a vector $a\in{\mathbb{F}}_{q}^{n}$ we define its empirical distribution
${\mathsf{Emp}_{a}}$ over ${\mathbb{F}}_{q}$ by

${\mathsf{Emp}_{a}}(x)=\Pr_{i\in[n]}\left[a_{i}=x\right]\enspace.$

More generally, given $A\in{\mathbb{F}}_{q}^{n\times b}$, let
${\mathsf{Emp}_{A}}$ denote its _empirical row distribution_ , that is, the
distribution over ${\mathbb{F}}_{q}^{b}$ defined by

${\mathsf{Emp}_{A}}(x)=\Pr_{i\in[n]}\left[A_{i}=x\right]\enspace,$

where $A_{i}$ denotes the $i$’th row of $A$.

######  Fact 4.7 ([CT06, Thm. 11.1.4]).

Let $X\in{\mathbb{F}}_{q}^{n\times b}$ have rows sampled identically and
independently from some distribution $\sigma$ over ${\mathbb{F}}_{q}^{b}$.
Then, for any distribution $\tau$ over ${\mathbb{F}}_{q}^{b}$,

$\mathrm{Pr}\left[{\mathsf{Emp}_{A}}=\tau\right]\leq
q^{-{D_{\mathrm{KL}}}_{q}\left(\tau\parallel\sigma\right)\cdot n}\enspace.$

######  Definition 4.8.

Let $\tau$ be a distribution over ${\mathbb{F}}_{q}^{b}$. We denote
$\dim(\tau)=\dim\mathrm{supp}(\tau)$. If $\dim(\tau)=b$, we say that $\tau$ is
a full-rank distribution.

######  Definition 4.9 (Matrix of a particular distribution).

Let $\tau$ be a distribution over ${\mathbb{F}}_{q}^{b}$ (where
$b\in\mathbb{N}$). For $n\in\mathbb{N}$, we denote

$\mathcal{M}_{n,\tau}=\left\\{A\in{\mathbb{F}}_{q}^{n\times
b}\mid{\mathsf{Emp}_{A}}=\tau\right\\}\enspace.$

A distribution $\tau$ over ${\mathbb{F}}_{q}^{b}$ is said to be $n$-feasible
if $\tau(x)\cdot n$ is an integer for all $x\in{\mathbb{F}}_{q}^{b}$. Observe
that any $n$-feasible distribution over ${\mathbb{F}}_{q}^{b}$ corresponds to
a partition of $n$ identical balls into $q^{b}$ buckets. The bound below thus
follows immediately.

######  Fact 4.10.

The number of $n$-feasible distributions over ${\mathbb{F}}_{q}^{b}$ is at
most $(n+1)^{q^{b}}$.

Clearly, $n$-feasibility of $\tau$ is a necessary condition for
$\mathcal{M}_{n,\tau}$ to be nonempty. When this condition holds,
$|\mathcal{M}_{n,\tau}|$ is equal to the multinomial coefficient
$\frac{n!}{\prod_{x\in{\mathbb{F}}_{q}^{b}}(\tau(x)n)!}$. By standard bounds
on multinomial coefficients, we have

$n^{-O(q^{b})}\cdot q^{n\cdot
H_{q}(\tau)}\leq\left|\mathcal{M}_{n,\tau}\right|\leq q^{n\cdot
H_{q}(\tau)}\enspace.$ (10)

####  4.6.1 The Fourier transform of an empirical distribution

We record several useful properties of the function
$\widehat{{\mathsf{Emp}_{A}}}$ for a given matrix $A$. The following is
immediate.

######  Fact 4.11.

A vector $u\in{\mathbb{F}}_{q}^{n}$ is $\eta$-biased ($\eta>0$) if and only if
$\left|\widehat{{\mathsf{Emp}_{u}}}(a)\right|\leq\eta$ for all
$a\in{\mathbb{F}}_{q}^{*}$.

The following identity shows that the Fourier transform of
${\mathsf{Emp}_{A}}$ (where $A\in{\mathbb{F}}_{q}^{n\times b}$) is in fact
composed of the Fourier transforms of ${\mathsf{Emp}_{Ay}}$ over
$y\in{\mathbb{F}}_{q}^{b}$. Let $a\in{\mathbb{F}}_{q}$. Then,

$\widehat{{\mathsf{Emp}_{A}}}(ay)=\sum_{x\in{\mathbb{F}}_{q}^{b}}{\mathsf{Emp}_{A}}(x)\omega^{-\mathrm{tr}(a\left\langle
x,y\right\rangle)}=\mathbb{E}_{x\sim{\mathsf{Emp}_{A}}}\left[\omega^{-\mathrm{tr}(a\left\langle
x,y\right\rangle)}\right]=\mathbb{E}_{z\sim{\mathsf{Emp}_{Ay}}}\left[\omega^{-\mathrm{tr}(az)}\right]=\widehat{{\mathsf{Emp}_{Ay}}}(a)\enspace.$
(11)

By 4.5, the normalized Hamming Weight of a vector $u\in{\mathbb{F}}_{q}^{n}$
can be conveniently expressed in terms of the Fourier transform of
${\mathsf{Emp}_{u}}$.

$\operatorname{wt}(u)=\sum_{x\in{\mathbb{F}}_{q}}\mathbf{1}_{x\neq
0}\cdot{\mathsf{Emp}_{u}}(x)=\frac{q-1}{q}\cdot\widehat{{\mathsf{Emp}_{u}}}(0)-\frac{1}{q}\cdot\sum_{a\in{\mathbb{F}}_{q}^{*}}\widehat{{\mathsf{Emp}_{u}}}(a)=\frac{q-1}{q}-\frac{1}{q}\cdot\sum_{a\in{\mathbb{F}}_{q}^{*}}\widehat{{\mathsf{Emp}_{u}}}(a).$
(12)

This yields the following relation between bias and weight.

######  Lemma 4.12.

Let $u\in{\mathbb{F}}_{q}^{n}$ be $\eta$-biased for some $\eta>0$. Then

$\frac{q-1}{q}(1-\eta)\leq\operatorname{wt}(u)\leq\frac{q-1}{q}(1+\eta)\enspace.$

###### Proof.

By Eqs. 12 and 4.11,

$\left|\operatorname{wt}(u)-\frac{q-1}{q}\right|=\left|\frac{1}{q}\cdot\sum_{a\in{\mathbb{F}}_{q}^{*}}\widehat{{\mathsf{Emp}_{u}}}(a)\right|\leq\frac{q-1}{q}\cdot\eta\enspace.\qed$

We have the following immediate conclusion.

######  Lemma 4.13.

For any $\eta\geq 0$, an $\eta$-biased code also has $\eta$-optimal distance.

##  5 A random puncturing of a near-optimal-distance code is likely to be
list-decodable

Our goal in this section is to prove Theorem 5 on the list-decodability of
random puncturings of any mother code of sufficiently high distance.

###  5.1 GHK list-decodability bound for random linear codes revisited

The main result of [GHK11] gives bounds on the list-size for list-decoding of
RLCs up to capacity. Here, we go deeper and slightly reformulate111111See
Remark 5.2 for the differences in our formulation. the main technical claim of
that paper.

######  Theorem 5.1 ([GHK11, Thm. 6.1]).

Let $q$ be a prime power and let $\rho\in(0,1-1/q)$. Then, there is a constant
$K^{\prime}=K^{\prime}_{\rho,q}\geq 1$ such that, for all $b,L\in\mathbb{N}$,
we have

$\left|\left\\{A\in{\mathbb{F}}_{q}^{n\times b}\mid A\text{ is
$(\rho,L+1)$-span-clustered}\right\\}\right|\leq q^{(bh_{q}(\rho)-4)\cdot n}$

whenever $L\geq K^{\prime}\cdot b$ and $n$ is large enough, and

$\left|\left\\{A\in{\mathbb{F}}_{q}^{n\times b}\mid A\text{ is
$(\rho,L+1)$-span-clustered}\right\\}\right|\leq q^{(bh_{q}(\rho)+1)\cdot n}$
(13)

in general.

Furthermore, one can take

$K^{\prime}\leq\mathrm{exp}\left(O\left(\frac{(\log_{2}q)^{2}}{\min\left\\{(1-1/q-\rho)^{2},\rho\right\\}}\right)\right)\enspace.$
(14)

######  Remark 5.2.

There are several differences between our formulation of the theorem and the
one that appears in [GHK11]. We list and justify them here.

  1. (i)

The random vectors $X_{1},\dotsc,X_{\ell}$ from the original formulation have
become the columns of the matrix $A$, and we changed the name $\ell$ to $b$.

  2. (ii)

The original statement of [GHK11, Thm. 6.1 ] only deals with matrices whose
span contains a large set clustered around $0$. In our statement we already
apply the reduction to a ball with arbitrary center, which appears in [GHK11,
Thm. 2.1].

  3. (iii)

Eq. 13 is a rather naive bound, originally derived as part of the proof of
[GHK11, Thm. 2.1].

  4. (iv)

The asymptotic statement about $K^{\prime}_{\rho,q}$ comes from inspecting the
proof in [GHK11]. Specifically, in the notation of that paper, [GHK11, Lem.
6.3] yields a $2$-increasing chain of length $d=\Omega(\log_{q}K^{\prime})$
whenever $L\geq K^{\prime}\cdot b$. The exponent in the $q$-ary analog of
[GHK11, Lem 4.1] satisfies
$\delta_{p}=\Theta\left(\tfrac{\min\left\\{\rho,\left(1-\frac{1}{q}-\rho\right)^{2}\right\\}}{\log_{2}q}\right)$.
Finally, the requirement in [GHK11, Thm. 6.1] is that $K^{\prime}$ be large
enough so that $d\cdot\delta_{p}\geq\Omega(1)$.

It will be convenient to formulate a corollary from Theorem 5.1 in terms of
the row-distributions of certain matrices.

######  Definition 5.3.

Fix a prime power $q$. Let $b,n\in N$ and let $\tau$ be an $n$-feasible
distribution over ${\mathbb{F}}_{q}^{b}$. If a matrix
$A\in\mathcal{M}_{n,\tau}$ is $(\rho,L+1)$-span-clustered, we say that $\tau$
is $(\rho,L+1)$-span-clustered (with regard to $n$).

######  Remark 5.4.

Observe that the notion of $\tau$ being $(\rho,L+1)$-span clustered is well
defined, and in particular does not depend on the choice of $A$ in Definition
5.3. In other words, either every matrix in $\mathcal{M}_{n,\tau}$ is
$(\rho,L+1)$-span-clustered, or none of them are. Indeed, suppose that
$A\in{\mathbb{F}}_{q}^{n\times b}$ is $(\rho,L+1)$-span-clustered with regard
to some center $z\in{\mathbb{F}}_{q}^{n}$, and let $B$ be a matrix obtained
from $A$ by permuting the rows of the latter according to some permutation
$\pi$ over $[n]$. Then, $B$ is $(\rho,L+1)$-span-clustered with regard to the
center vector resulting from applying $\pi$ to $z$.

The above observation is a result of the fact that containing a
$\left(\rho,L+1\right)\text{-span-clustered}$ matrix is a row-symmetric code
property (see Definition 2.5).

######  Corollary 5.5.

In the setting of Theorem 5.1, every $(\rho,L+1$)-span-clustered (with regard
to $n$), $n$-feasible distribution $\tau$ over ${\mathbb{F}}_{q}^{b}$
satisfies

$H_{q}(\tau)\leq
b\cdot\left(h_{q}(\rho)+\frac{5K^{\prime}_{\rho,q}}{L}\right)-3\enspace.$

for every $b$ and $n$ such that
$\frac{n}{\log_{q}n}\geq\omega\left(q^{L+1}\right)$.

###### Proof.

By Remark 5.4,
$\mathcal{M}_{n,\tau}\subseteq\left\\{A\in{\mathbb{F}}_{q}^{n\times b}\mid
A\text{ is $(\rho,L+1)$-span-clustered}\right\\}$. Thus, Eqs. 10 and 5.1 yield
the following:

##### If $L\geq K^{\prime}_{\rho,q}\cdot b$:

$H_{q}(\tau)\leq\log_{q}\left|\mathcal{M}_{n,\tau}\right|+O\left(\frac{q^{b}\cdot\log_{q}n}{n}\right)\leq
bh_{q}(\rho)-4+O\left(\frac{q^{b}\cdot\log_{q}n}{n}\right)$

##### If $L<K^{\prime}_{\rho,q}\cdot b$:

$\displaystyle H_{q}(\tau)$
$\displaystyle\leq\log_{q}\left|\mathcal{M}_{n,\tau}\right|+O\left(\frac{q^{b}\cdot\log_{q}n}{n}\right)\leq
bh_{q}(\rho)+1+O\left(\frac{q^{b}\cdot\log_{q}n}{n}\right)$ $\displaystyle\leq
bh_{q}(\rho)+\frac{5bK^{\prime}_{\rho,q}}{L}-4+O\left(\frac{q^{b}\cdot\log_{q}n}{n}\right)\enspace.$

The claim now follows from our assumption that
$\frac{n}{\log_{q}n}\geq\omega\left(q^{L+1}\right)$. ∎

###  5.2 Proof of Theorem 5

We now turn to proving Theorem 5, restated here. See 5

Before proving the theorem, we compare it to several known results about list-
decodability of RLCs. By the List-Decoding Capacity Theorem, Theorem 5
achieves the optimal trade-off between $q$, $\rho$ and $R$. We thus turn to
discuss the secondary trade-off, which involves the former three parameters
and the _list-size_ $L$. As mentioned in Section 2.5, Theorem 5 is derived by
reduction to the result of [GHK11] on list-decodability of RLCs. The main
theorem of [GHK11] states that a RLC of rate
$R=1-h_{q}(\rho)-\frac{K^{\prime}_{\rho,q}}{L}$ is with high probability is
$\left(\rho,L\right)\text{-list-decodable}$, where
$K^{\prime}_{\rho,q}\leq\mathrm{exp}\left(O\left(\frac{(\log
q)^{2}}{\min\left\\{(1-1/q-\rho)^{2},\rho\right\\}}\right)\right)$ is
proportional to the constant $K_{\rho,q}$ that appears in Theorem 5. Denoting
the _gap-to-capacity of the rate_ by $\varepsilon=1-h_{q}(\rho)-R$, [GHK11]
shows that an RLC of rate $R$ is almost surely
$\left(\rho,L\right)\text{-list-decodable}$ with
$L\approx\frac{K^{\prime}_{\rho,q}}{\varepsilon}$. In Theorem 5, we have
$\varepsilon=\frac{K_{\rho,q}}{L}$, so
$L=\frac{K_{\rho,q}}{\varepsilon}=O\left(\frac{K^{\prime}_{\rho,q}}{\varepsilon}\right)$.
Thus, we can informally state Theorem 5 as “A random puncturing of a code of
near-optimal distance is very likely to be list-decodable up to capacity, with
a similar list-size trade-off to that guaranteed by [GHK11] for RLCs.”

The list-size $L$ guaranteed by Theorem 5 inherits some desirable properties
from [GHK11]: it is constant in terms of $n$, and has linear dependence on
$\frac{1}{\varepsilon}$, which is tight for RLCs [GN14, Thm. 16]. As for the
dependence on $q$ and $\rho$, we get good list-size bounds when $q$ is not too
large and $\rho$ is bounded away from $0$ and $1-\frac{1}{q}$, but,
unfortunately, the constant $K_{\rho,q}$ grows exponentially as $\rho\to
1-\frac{1}{q}$. In comparison with [GHK11], other works on RLC list-
decodability are more specialized, and give tighter upper bounds on the list-
size in specific regimes. Notably, [Woo13] does well when $\rho$ is large and
$\varepsilon$ is of similar magnitude to $R$, and [LW21] gives an extremely
tight upper bound (see [GLMRSW20]) on the list-size for every $\rho$ and
$\varepsilon$, when $q=2$.

We note that, while Theorem 5 only achieves the analogue of [GHK11] for
randomly punctured codes, Theorems 1 and 4, with their somewhat stronger
hypotheses, achieve (in particular) analogues of all known _and future_
positive results about list-decodability of RLCs. The obstacle to concluding
such a broad result solely from the hypothesis of Theorem 5 is discussed in
Remark 6.14.

Our proof of Theorem 5 relies on the following lemma, whose proof we defer to
Section 5.3.

######  Lemma 5.6 (Puncturings of large-distance codes are locally similar in
expectation to random linear codes).

Fix $b\in\mathbb{N}$ and a full-rank distribution $\tau$ over
${\mathbb{F}}_{q}^{b}$. Let $\mathcal{D}\subseteq{\mathbb{F}}_{q}^{m}$ be a
linear code of $\eta$-optimal distance ($\eta\geq 0$). Let
$\Lambda\sim\mathsf{U}(\Gamma_{n})$ and, independently, let $\varphi$ be a
random $(m\to n)$ puncturing map. Denote $R=\frac{\log_{q}|\mathcal{D}|}{n}$.
Then,

$\mathbb{E}\left[\left|\left\\{A\in\mathcal{M}_{n,\tau}\mid
A\subseteq\Lambda\cdot\varphi(\mathcal{D})\right\\}\right|\right]\leq\mathrm{exp}_{q}\left(n\cdot\left(H_{q}(\tau)-(1-R)b+\log_{q}\left(1+\eta
q^{b}\right)+\log_{q}2\right)\right)$

######  Remark 5.7.

Lemma 5.6 bounds the expected number of $\tau$-distributed matrices in the
code $\Lambda\cdot\varphi(\mathcal{D})$. The lemma says that this number is
not much larger than the expected number of $\tau$-distributed matrices in a
random linear code of similar rate. Indeed, for a given matrix $A$, the
probability of $A$ being contained in the random linear code
$C_{\mathrm{RLC}}^{n,q}(R)$ is $q^{-n(1-R)\cdot\operatorname{rank}(A)}$. Thus,
by Eq. 10,

$\mathbb{E}\left[\left|\left\\{A\in\mathcal{M}_{n,\tau}\mid A\subseteq
C_{\mathrm{RLC}}^{n,q}(R)\right\\}\right|\right]=\left|\mathcal{M}_{n,\tau}\right|\cdot
q^{n(R-1)\cdot b}\approx q^{n\left(H_{q}(\tau)-(1-R)b\right)}\enspace.$

Using Lemma 5.6, we conclude Theorem 5 from Theorem 5.1.

###### Proof of Theorem 5.

Take $K_{\rho,q}=5K^{\prime}$, where $K^{\prime}_{\rho,q}$ is as in Theorem
5.1. We need to show that

$\mathrm{Pr}\left[\mathcal{C}\text{ is not }\left(\rho,L\right)\text{-list-
decodable}\right]\leq q^{-\Omega(\varepsilon n)}.$

Since being not $\left(\rho,L\right)\text{-list-decodable}$ is a scalar-
invariant property (see Definitions 2.8 and 4.3), it suffices to show instead
that

$\mathrm{Pr}\left[\Lambda\mathcal{C}\text{ is not
}\left(\rho,L\right)\text{-list-decodable}\right]\leq q^{-\Omega(\varepsilon
n)}\enspace,$ (15)

where the matrix $\Lambda$ is sampled uniformly from $\Gamma_{n}$.

Now, if $\Lambda\mathcal{C}$ is _not_ $\left(\rho,L\right)\text{-list-
decodable}$, then $\Lambda\mathcal{C}$ contains some $(\rho,L+1)$-span-
clustered matrix $A\in{\mathbb{F}}_{q}^{n\times b}$ for some $b$,
$\log_{q}(L+1)\leq b\leq L+1$. Hence,

$\displaystyle\mathrm{Pr}\left[\Lambda\mathcal{C}\text{ is not
}\left(\rho,L\right)\text{-list-decodable}\right]$
$\displaystyle\leq\sum_{b=\lceil\log_{q}(L+1)\rceil}^{L+1}\mathrm{Pr}\left[\exists
A\in{\mathbb{F}}_{q}^{n\times b}\text{ s.t. }A\text{ is
}\left(\rho,L+1\right)\text{-span-clustered}\text{ and
}A\subseteq\Lambda\mathcal{C}\right]$
$\displaystyle\leq\sum_{b=\lceil\log_{q}(L+1)\rceil}^{L+1}\mathbb{E}\left[\left|\left\\{A\in{\mathbb{F}}_{q}^{n\times
b}\mid A\text{ is }\left(\rho,L+1\right)\text{-span-clustered}\text{ and
}A\subseteq\Lambda\mathcal{C}\right\\}\right|\right]\enspace.$

By Remark 5.4, we can write

$\left\\{A\in{\mathbb{F}}_{q}^{n\times b}\mid A\text{ is
}\left(\rho,L+1\right)\text{-span-clustered}\right\\}=\bigcup_{\tau\in
T_{b}}\mathcal{M}_{n,\tau}$

where $T_{b}$ is a set of $n$-feasible distributions over
${\mathbb{F}}_{q}^{b}$. Therefore, by Lemma 5.6 and our assumption that
$\eta\leq q^{-{L+1}}\leq q^{-b}$, the probability that
$\Lambda\mathcal{C}\text{ is not }\left(\rho,L\right)\text{-list-decodable}$
is at most

$\displaystyle\sum_{b=\lceil\log_{q}(L+1)\rceil}^{L+1}\sum_{\tau\in
T_{b}}\mathbb{E}\left[\left|\left\\{A\in\mathcal{M}_{n,\tau}\mid
A\subseteq\Lambda\mathcal{C}\right\\}\right|\right]$
$\displaystyle~{}\leq\sum_{b=\lceil\log_{q}(L+1)\rceil}^{L+1}\sum_{\tau\in
T_{b}}\mathrm{exp}_{q}\left(n\cdot\left(H_{q}(\tau)-(1-R)b+\log_{q}(1+\eta
q^{b})+\log_{q}2\right)\right)$
$\displaystyle~{}\leq\sum_{b=\lceil\log_{q}(L+1)\rceil}^{L+1}\sum_{\tau\in
T_{b}}\mathrm{exp}_{q}\left(n\cdot\left(H_{q}(\tau)-(1-R)b+2\right)\right)\enspace.$

By Corollary 5.5, each term of the inner sum is at most $q^{-n}$. Therefore,
by 4.10,

$\mathrm{Pr}\left[\Lambda\mathcal{C}\text{ is not
}\left(\rho,L\right)\text{-list-
decodable}\right]\leq\sum_{b=\lceil\log_{q}(L+1)\rceil}^{L+1}\sum_{\tau\in
T_{b}}q^{-n}\leq q^{-n}\sum_{b=1}^{L+1}(n+1)^{q^{b}}\leq
q^{-n}(L+1)(n+1)^{q^{L+1}}\enspace,$

and the theorem follows due to our assumption that
$\frac{n}{\log_{q}n}\geq\omega\left(q^{L+1}\right)$. ∎

###  5.3 Proof of Lemma 5.6

Lemma 5.6 follows from Lemmas 5.8, 5.9 and 5.10, stated and proven below. The
proof of Lemma 5.6 is then completed at the end of this section.

Lemma 5.8 is a variation of the _Vazirani XOR-Lemma_ (see [Gol11], and Lemma
3.1 for a special case). Given a distribution $\sigma$ over
${\mathbb{F}}_{q}^{b}$ , the XOR-Lemma relates the _total-variation distance_
of $\sigma$ from the uniform distribution over ${\mathbb{F}}_{q}^{b}$, to the
maximum of $\left|\widehat{\sigma}(y)\right|$ over all $y\neq 0$. In Lemma
5.8, rather than taking a maximum, we consider the $\ell_{1}$ norm of
$\widehat{\sigma}$, which yields a tighter bound when only a small number of
entries of $\widehat{\sigma}$ are large in absolute value.

######  Lemma 5.8.

Fix a prime power $q$, and $b\in\mathbb{N}$. Let $\sigma$ be a distribution
over ${\mathbb{F}}_{q}^{L}$ and let $f:{\mathbb{F}}_{q}^{b}\to{\mathbb{R}}$ be
a non-negative function. Then,

$\mathbb{E}_{x\sim\sigma}\left[f(x)\right]\leq\left(\sum_{y\in{\mathbb{F}}_{q}^{b}}\left|\widehat{\sigma}(y)\right|\right)\cdot\mathbb{E}_{x\sim\mathsf{U}({\mathbb{F}}_{q}^{b})}\left[f(x)\right]\enspace.$

###### Proof.

We have

$\sigma(x)=q^{-b}\sum_{y\in{\mathbb{F}}_{q}^{b}}\widehat{\sigma}(y)\omega^{-\mathrm{tr}(\left\langle
x,y\right\rangle)}\leq
q^{-b}\sum_{y\in{\mathbb{F}}_{q}^{b}}\left|\widehat{\sigma}(y)\right|$

for all $x\in{\mathbb{F}}_{q}^{b}$. So

$\mathbb{E}_{x\sim\sigma}\left[f(x)\right]=\sum_{x\in{\mathbb{F}}_{q}^{b}}\sigma(x)f(x)\leq
q^{-b}\left(\sum_{y\in{\mathbb{F}}_{q}^{b}}\left|\widehat{\sigma}(y)\right|\right)\cdot\left(\sum_{x\in{\mathbb{F}}_{q}^{b}}f(x)\right)=\left(\sum_{y\in{\mathbb{F}}_{q}^{b}}\left|\widehat{\sigma}(y)\right|\right)\cdot\mathbb{E}_{x\sim\mathsf{U}({\mathbb{F}}_{q}^{b})}\left[f(x)\right]\enspace.\qed$

We next bound the expectation of an arbitrary non-negative test function over
the empirical row-distribution of a given matrix $B$, assuming that the
column-span of $B$ has good bias or distance. The bias based bound is an
immediate application of Lemma 5.8. The weight based bound requires an
additional trick, and only yields a result relating to the row-distribution of
$B^{*}$ rather than $B$ itself (recall Definition 4.2 for a reminder about
$B^{*}$). One reason for the difference between the two cases is that under
the weight-based hypothesis we have an upper bound only on the entries of the
Fourier transform (Eq. 18), rather than on their absolute value.

######  Lemma 5.9.

Let $B\in{\mathbb{F}}_{q}^{m\times b}$ have $\operatorname{rank}B=b$, and let
$f:{\mathbb{F}}_{q}^{b}\to{\mathbb{R}}$ be a non-negative function. Then, the
following holds for all $\eta\geq 0$:

  1. 1.

Suppose that the column-span of $B$ (as a code in ${\mathbb{F}}_{q}^{m}$) is
$\eta$-biased. Then,

$\mathbb{E}_{x\sim{\mathsf{Emp}_{B}}}\left[f(x)\right]\leq(1+q^{b}\eta)\cdot\mathbb{E}_{x\sim\mathsf{U}({\mathbb{F}}_{q}^{b})}\left[f(x)\right]\enspace.$

  2. 2.

Suppose that the column-span of $B$ has $\eta$-optimal distance. Then,

$\mathbb{E}_{x\sim{\mathsf{Emp}_{B^{*}}}}\left[f(x)\right]\leq
2(1+q^{b}\eta)\cdot\mathbb{E}_{x\sim\mathsf{U}({\mathbb{F}}_{q}^{b})}\left[f(x)\right]\enspace.$

###### Proof.

We first prove Item 1. Hence, by Lemma 5.8 it suffices to show that

$\sum_{y\in{\mathbb{F}}_{q}^{b}}\left|\widehat{{\mathsf{Emp}_{B}}}(y)\right|\leq
1+q^{b}\eta\enspace.$

By Eq. 11, the above is equivalent to

$\sum_{y\in{\mathbb{F}}_{q}^{b}}\left|\widehat{{\mathsf{Emp}_{By}}}(1)\right|\leq
1+q^{b}\eta\enspace.$ (16)

For $y=0$ we have
$\widehat{{\mathsf{Emp}_{By}}}(1)=\widehat{{\mathsf{Emp}_{0}}}(1)=1$. For any
$y\in{\mathbb{F}}_{q}^{b}\setminus\\{0\\}$, since $B$ has full column-rank,
$By$ is a non-zero codeword of $\mathcal{D}$. By hypothesis, $By$ is
$\eta$-biased, so 4.11 yields
$\left|\widehat{{\mathsf{Emp}_{By}}}(1)\right|\leq\eta$, establishing Eq. 16.

We now turn to Item 2. Let $\sigma$ denote the distribution, over
${\mathbb{F}}_{q}^{b}$, of the random variable $a\cdot x$, where
$a\sim\mathsf{U}({\mathbb{F}}_{q}^{*})$ and $x$ is independently sampled from
${\mathsf{Emp}_{B}}$. By Lemma 5.8, to prove Item 2 it suffices to show that

$\sum_{y\in{\mathbb{F}}_{q}^{b}}\left|\widehat{\sigma}(y)\right|\leq
2\left(1+q^{b}\eta\right)\enspace.$ (17)

By Eq. 12 followed by Eq. 11,

$\operatorname{wt}(By)=\frac{q-1}{q}-\frac{1}{q}\cdot\sum_{a\in{\mathbb{F}}_{q}^{*}}\widehat{{\mathsf{Emp}_{By}}}(a)=\frac{q-1}{q}-\frac{1}{q}\cdot\sum_{a\in{\mathbb{F}}_{q}^{*}}\widehat{{\mathsf{Emp}_{B}}}(ay)=\frac{q-1}{q}\cdot\left(1-\widehat{\sigma}(y)\right)\enspace,$

so $\widehat{\sigma}(y)=1-\frac{q}{q-1}\cdot\operatorname{wt}(By)$.

In particular, if $y\neq 0$ then $By$ is a non-zero element in the column-span
of $B$. Hence, by hypothesis,

$\widehat{\sigma}(y)=1-\frac{q}{q-1}\cdot\operatorname{wt}(By)\leq\eta\enspace.$
(18)

Let $P=\\{y\in{\mathbb{F}}_{q}^{b}\mid\widehat{\sigma}(y)\geq 0\\}$ and
$N={\mathbb{F}}_{q}^{b}\setminus P$. By Eq. 18,

$\sum_{y\in P\setminus\\{0\\}}\widehat{\sigma}(y)\leq q^{b}\eta\enspace.$

Note that $\widehat{\sigma}(0)=\sum_{x\in{\mathbb{F}}_{q}^{b}}\sigma(x)=1$,
and thus,

$\sum_{y\in P}\widehat{\sigma}(y)=1+\sum_{y\in
P\setminus\\{0\\}}\widehat{\sigma}(y)\leq 1+q^{b}\eta\enspace.$

Consequently,

$0\leq
q^{b}\cdot\sigma(0)=\sum_{y\in{\mathbb{F}}_{q}^{b}}\widehat{\sigma}(y)=\sum_{y\in
P}\widehat{\sigma}(y)+\sum_{y\in N}\widehat{\sigma}(y)\leq
1+q^{b}\eta+\sum_{y\in\mathbb{N}}\widehat{\sigma}(y)$

and so,

$\sum_{y\in N}\left|\widehat{\sigma}(y)\right|=-\sum_{y\in
N}\widehat{\sigma}(y)\leq 1+q^{b}\eta\enspace.$

Eq. 17 now follows since

$\sum_{y\in{\mathbb{F}}_{q}^{b}}\left|\widehat{\sigma}(y)\right|=\sum_{y\in
P}\left|\widehat{\sigma}(y)\right|+\sum_{y\in
N}\left|\widehat{\sigma}(y)\right|\leq 2(1+q^{b}\eta)\enspace.\qed$

Lemma 5.10 bounds the probability of a random puncturing of a given matrix $B$
having a certain empirical distribution $\tau$. Due to the concavity argument
in Eq. 20, this lemma gives tighter bounds when ${\mathsf{Emp}_{B}}$ is close
to the uniform distribution over ${\mathbb{F}}_{q}^{b}$. Notably, as Lemma 5.9
shows, good bias or similar properties of the column-span of $B$ ensure that
${\mathsf{Emp}_{B}}$ is indeed close to uniform.

######  Lemma 5.10.

Fix some distribution $\tau$ over ${\mathbb{F}}_{q}^{b}$. Let
$B\in{\mathbb{F}}_{q}^{m\times b}$ have $\operatorname{rank}B=b$. Let
$\varphi:{\mathbb{F}}_{q}^{m}\to{\mathbb{F}}_{q}^{n}$ be a random puncturing
map. Then,

$\mathrm{Pr}\left[\varphi(B)\in\mathcal{M}_{n,\tau}\right]\leq\mathrm{exp}_{q}\left(n\left(\log_{q}\mathbb{E}_{x\sim{\mathsf{Emp}_{B}}}\left[\tau(x)\right]+H_{q}(\tau)\right)\right)\enspace.$

###### Proof.

By 4.7,

$\mathrm{Pr}\left[\varphi(B)\in\mathcal{M}_{n,\tau}\right]=\mathrm{Pr}\left[{\mathsf{Emp}_{\varphi(B)}}=\tau\right]\leq
q^{-n\cdot{D_{\mathrm{KL}}}_{q}\left(\tau\parallel{\mathsf{Emp}_{B}}\right)}\enspace.$
(19)

By concavity of $\log$,

$\displaystyle{D_{\mathrm{KL}}}_{q}\left(\tau\parallel{\mathsf{Emp}_{B}}\right)$
$\displaystyle=\sum_{x\in{\mathbb{F}}_{q}^{b}}\tau(x)\log_{q}\frac{\tau(x)}{{{\mathsf{Emp}_{B}}}(x)}=-H_{q}(\tau)-\sum_{x\in{\mathbb{F}}_{q}^{b}}\tau(x)\log_{q}{{\mathsf{Emp}_{B}}}(x)$
$\displaystyle\geq-
H_{q}(\tau)-\log_{q}\mathbb{E}_{x\sim{\mathsf{Emp}_{B}}}\left[\tau(x)\right]\enspace.$
(20)

The claim follows from Eq. 19 and Eq. 20. ∎

###### Proof of Lemma 5.6.

By Observation 4.3, $\Lambda\cdot\varphi(\mathcal{D})$ is distributed
identically to $\varphi^{*}(\mathcal{D}^{*})$, where $\varphi^{*}$ is a random
$((q-1)m\to n)$ puncturing map. Thus,

$\displaystyle\mathbb{E}\left[\left|\left\\{A\in\mathcal{M}_{n,\tau}\mid
A\subseteq\Lambda\cdot\varphi(\mathcal{D})\right\\}\right|\right]$
$\displaystyle=\mathbb{E}\left[\left|\left\\{A\in\mathcal{M}_{n,\tau}\mid
A\subseteq\varphi^{*}(\mathcal{D}^{*})\right\\}\right|\right]$
$\displaystyle\leq\mathbb{E}\left[\left|\left\\{B\in{\mathbb{F}}_{q}^{m\times
b}\mid B\subseteq\mathcal{D}\text{ and
}\varphi^{*}(B^{*})\in\mathcal{M}_{n,\tau}\right\\}\right|\right]\enspace.$
(21)

We proceed to bound the expectation of the right-hand side.

Suppose that $\varphi^{*}(B^{*})\in\mathcal{M}_{n,\tau}$. Because $\tau$ is of
full-rank, we have
$\operatorname{rank}B=\operatorname{rank}B^{*}\geq\operatorname{rank}\varphi^{*}(B^{*})=b$,
so $\operatorname{rank}B=b$.

Let $B\in{\mathbb{F}}_{q}^{m\times b}$ such that $\operatorname{rank}B=b$ and
$B\subseteq\mathcal{D}$. Since the column-span of $B$ is contained in
$\mathcal{D}$, it is of $\eta$-optimal distance. Hence, by Item 2 of Lemma
5.9,

$\mathbb{E}_{x\sim{\mathsf{Emp}_{B^{*}}}}\left[\tau(x)\right]\leq\Upsilon\enspace,$
(22)

where $\Upsilon=2q^{-b}\left(1+q^{b}\eta\right)$. Lemma 5.10 yields

$\displaystyle\mathbb{E}\left[\left|\left\\{B\in{\mathbb{F}}_{q}^{m\times
b}\mid B\subseteq\mathcal{D}\text{ and
}\varphi^{*}(B^{*})\in\mathcal{M}_{n,\tau}\right\\}\right|\right]$
$\displaystyle=\sum_{\begin{subarray}{c}B\in{\mathbb{F}}_{q}^{m\times b}\\\
B\subseteq\mathcal{D}\\\
\operatorname{rank}B=b\end{subarray}}{\Pr_{\Lambda,\varphi}\left[\varphi^{*}(B^{*})\in\mathcal{M}_{n,\tau}\right]}$
$\displaystyle\leq
q^{bRn}\cdot\mathrm{exp}_{q}\left(n\left(\log_{q}\Upsilon+H_{q}(\tau)\right)\right)\enspace,$
(23)

and the claim follows from Eqs. 21, 22 and 23. ∎

##  6 Random puncturings of certain codes are locally-similar to RLCs

In this section we prove Theorems 1 and 4, restated below.

See 1 See 4

###  6.1 Monotone-increasing properties and minimal sets

A monotone-increasing property $\mathcal{P}$ of codes has a unique minimal-set
$\mathcal{M}_{\mathcal{P}}$, namely, a matrix
$A\subseteq{\mathbb{F}}_{q}^{n\times b}$ ($b\in\mathbb{N}$) of full column-
rank belongs to $\mathcal{M}_{\mathcal{P}}$ if the code consisting of the
column-span of $A$ satisfies $\mathcal{P}$, but no proper linear subspace of
that code does so.

######  Example 6.1 (Minimal set for list-decodability).

Fix a prime power $q$, $n,L\in\mathbb{N}$ and $\rho\in[0,1]$. Consider the
monotone-increasing property $\mathcal{P}$ consisting of all linear codes in
${\mathbb{F}}_{q}^{n}$ that are not $\left(\rho,L\right)\text{-list-
decodable}$. Then,

$\mathcal{M}_{\mathcal{P}}=\left\\{A\subseteq{\mathbb{F}}_{q}^{n\times b}\mid
b\in\mathbb{N},~{}~{}~{}A\text{ is }\left(\rho,L+1\right)\text{-span-
clustered}\right\\}\enspace.$

We can reformulate the notions of local, row-symmetric and scalar-invariant
monotone-increasing properties in terms of the minimal set
$\mathcal{M}_{\mathcal{P}}$ (see Definitions 2.5 and 2.8).

######  Observation 6.2 (Local, row-symmetric and scalar-invariant properties
in terms of $\mathcal{M}_{\mathcal{P}}$).

Let $\mathcal{P}$ be a monotone-increasing property of linear codes in
${\mathbb{F}}_{q}^{n}$.

  1. 1.

Fix $b\in\mathbb{N}$. Then, $\mathcal{P}$ is $b$-local if and only every
matrix in $\mathcal{M}_{\mathcal{P}}$ has at most $b$ columns.

  2. 2.

The property $\mathcal{P}$ is row-symmetric if and only if, for each
$A\in\mathcal{M}_{\mathcal{P}}$, it holds that every matrix obtained by
permuting the rows of $A$ also belongs to $\mathcal{M}_{\mathcal{P}}$.

  3. 3.

The property $\mathcal{P}$ is scalar-invariant if, for each
$A\in\mathcal{M}_{\mathcal{P}}$ and every full-rank diagonal matrix
$\Lambda\in{\mathbb{F}}_{q}^{n\times n}$ it holds that $\Lambda
A\in\mathcal{M}_{\mathcal{P}}$.

###  6.2 Row-symmetric $b$-local properties in terms of distributions over
${\mathbb{F}}_{q}^{b}$

Thresholds for row-symmetric and local properties can be characterized in
terms of empirical distributions of certain matrices. We recall this
connection.

######  Fact 6.3 ([GMRSW21, Fact 2.15]).

Let $\mathcal{P}$ be a monotone-increasing, $b$-local, row-symmetric property
over ${\mathbb{F}}_{q}^{n}$. Then, there exists a set
$\mathcal{T}_{\mathcal{P}}$ of distributions over ${\mathbb{F}}_{q}^{b}$ such
that $|\mathcal{T}_{\mathcal{P}}|\leq(n+1)^{q^{b}}$, and
$\mathcal{M}_{\mathcal{P}}=\bigcup_{\tau\in\mathcal{T}_{\mathcal{P}}}\mathcal{M}_{n,\tau}$.

######  Definition 6.4 (Implied distribution [MRRSW20, Def. 2.6]).

Let $\tau$ be a distribution over ${\mathbb{F}}_{q}^{b}$ and let
$D\in{\mathbb{F}}_{q}^{b\times a}$ such that $\operatorname{rank}D=a$ for some
$a\leq b$. The distribution (over ${\mathbb{F}}_{q}^{a}$) of the random vector
$xD$, where $x\sim\tau$ (note that $x$ is a row vector), is said to be
$\tau$-implied. We denote the set of $\tau$-implied distributions by
$\mathcal{I}_{\tau}$.

The motivation for Definition 6.4 is the following observation, which follows
immediately from the linearity of the code.

######  Observation 6.5.

Let $\tau$ be a distribution over ${\mathbb{F}}_{q}^{b}$, and let
$\tau^{\prime}\in\mathcal{I}_{\tau}$. Then, any linear code containing a
matrix in $\mathcal{M}_{n,\tau}$ must also contain some matrix in
$\mathcal{M}_{n,\tau^{\prime}}$.

We now have the following characterization of the threshold.

######  Theorem 6.6 ([MRRSW20, Thm. 2.8]).

121212The precise error term does not appear in the statement of this theorem
in [MRRSW20], but follows by inspecting the proof there.

Let $\mathcal{P}$ be a monotone-increasing, $b$-local, row-symmetric property
over ${\mathbb{F}}_{q}^{n}$, and let $\mathcal{T}_{\mathcal{P}}$ be as in 6.3.
Then,

${\mathrm{RLC}}(\mathcal{P})=\min_{\tau\in\mathcal{T}_{\mathcal{P}}}\max_{\tau^{\prime}\in\mathcal{I}_{\tau}}\left(1-\frac{H_{q}(\tau^{\prime})}{\dim(\tau^{\prime})}\right)\pm\frac{2q^{2b}\log_{q}n}{n}\enspace.$

Below, we demonstrate Footnote 12 via the property of list-recoverability. The
motivation is two-fold. First, list-recoverability itself is a property of
significant interest. Secondly, we will use Footnote 12 in the proof of
Theorems 1 and 4, and the special case of list-recoverability will help
familiarize the reader with this tool.

###  6.3 List-recoverability as a property of codes

List-recovery is an important generalization of list-decoding, where the
decoder is given not one, but a subset of $\ell$ symbols per position, and the
goal is to list all codewords which “miss” at most a fraction $\rho$ of these
subsets. We formally define the notion of (combinatorial) list-recoverability.

######  Definition 6.7.

Fix $1\leq\ell\leq q$ and let $\rho\in(0,1-\ell/q)$. The set $W$ is said to be
$(\rho,\ell)$-recovery-clustered if there exist sets
$Z_{1},\dots,Z_{n}\subseteq{\mathbb{F}}_{q}$, each of which is of size at most
$\ell$, such that $\left|\left\\{i\in[n]\mid u_{i}\notin
Z_{i}\right\\}\right|\leq\rho n$ for all $u\in W$. A code
$\mathcal{C}\subseteq{\mathbb{F}}_{q}^{n}$ is called
$\left(\rho,\ell,L\right)\text{-list-recoverable}$ if it does not contain any
$(\rho,\ell)$-recovery-clustered set of size $L+1$.

The following is immediate:

######  Observation 6.8.

Fix a prime power $q$, $1\leq\ell<q$, $\rho\in(0,1-\ell/q)$ and
$L\in\mathbb{N}$. Let $\mathcal{P}$ denote the monotone-increasing linear-code
property of codes in ${\mathbb{F}}_{q}^{n}$ that are _not_
$\left(\rho,\ell,L\right)\text{-list-recoverable}$. Then, $\mathcal{P}$ is
row-symmetric, $(L+1)$-local and scalar-invariant.

Say that a matrix $A\in{\mathbb{F}}_{q}^{n\times b}$ is
$\left(\rho,\ell,L\right)\text{-recovery-span-clustered}$ if the column span
of $A$ contains a $(\rho,\ell)$-clustered set of size $L+1$. Then,
$\mathcal{M}_{\mathcal{P}}$ is contained in the set of all
$\left(\rho,\ell,L\right)\text{-recovery-span-clustered}$ matrices.

Note that list-recovery generalizes list-decodability (Definition 2.4), i.e.,
a set $W$ is $\rho$-clustered if and only if it is $(\rho,1)$-recovery-
clustered. Likewise, a code is $\left(\rho,L\right)\text{-list-decodable}$ if
and only if it is $\left(\rho,1,L\right)\text{-list-recoverable}$.

The _List-Recovery Capacity Theorem_ [Res20, Thm. 2.4.12] gives the threshold
rate for list-recoverability as $R^{*}=1-h_{q,\ell}(\rho)$, where
$h_{q,\ell}(\rho)=\rho\log_{q}\left(\frac{q-\ell}{\rho}\right)+(1-\rho)\log_{q}\left(\frac{\ell}{1-\rho}\right)$.
Namely, for every $\varepsilon>0$ there exists a family of
$\left(\rho,\ell,O_{\rho,\ell,\varepsilon}(1)\right)\text{-list-recoverable}$
codes of rate at least $R^{*}-\varepsilon$ but, on the other hand, every
$\left(\rho,\ell,L\right)\text{-list-recoverable}$ family of codes of rate
$\geq R^{*}+\varepsilon$ has $L$ exponentially large in $\varepsilon n$.

We now use Footnote 12 to prove that RLCs achieve list-recovery
capacity131313Better lower bounds on ${\mathrm{RLC}}^{n,q}(\rho,\ell,L)$ are
known. See, e.g., [RW18]..

######  Proposition 6.9 (RLCs achieve list-recovery capacity).

For any fixed $q,\rho,\ell$ and $L$, we have

${\mathrm{RLC}}^{n,q}(\rho,\ell,L)\geq
1-h_{q,\ell}(\rho)-\frac{\ell}{\log_{q}L}-o_{n\to\infty}(1)\enspace.$

Proposition 6.9 means that RLCs get to within $\varepsilon$ of the capacity
rate for list-recovery with list-size $L\approx q^{\frac{\ell}{\varepsilon}}$.

To prove Proposition 6.9 we need the following claim.

######  Claim 6.10.

Let $B\in{\mathbb{F}}_{q}^{n\times b}$ be a matrix whose columns form a
$\left(\rho,\ell\right)\text{-recovery-clustered}$ set. Denote
$\tau={\mathsf{Emp}_{B}}$. Then, $H_{q}(\tau)\leq b\cdot
h_{q}(\ell,\rho)+\ell$, where
$h_{q,\ell}(\rho)=\rho\log_{q}\left(\frac{q-\ell}{\rho}\right)+(1-\rho)\log_{q}\left(\frac{\ell}{1-\rho}\right)$.

###### Proof.

Let $Z_{1},\dotsc,Z_{n}$ be subsets of ${\mathbb{F}}_{q}$, each of size
$\ell$, such that for all $j\in[b]$, we have $\left|\left\\{i\in[n]\mid
B_{i,j}\notin Z_{i}\right\\}\right|\leq\rho n$. Let $i$ be sampled uniformly
from $[n]$. We now have

$H_{q}(\tau)=H_{q}(B_{i})\leq H_{q}(B_{i},Z_{i})=H_{q}(Z_{i})+H_{q}(B_{i}\mid
Z_{i})\leq H_{q}(Z_{i})+\sum_{j=1}^{b}H_{q}(B_{i,j}\mid Z_{i}).$

The number of different options for $Z_{i}$ is $\binom{q}{\ell}$ so
$H_{q}(Z_{i})\leq\log_{q}(\binom{q}{\ell})\leq\ell$ . Let $\rho^{\prime}_{j}$
($j\in[b]$) denote the probability that $B_{i,j}\notin Z_{i}$, and note that
$\rho^{\prime}_{j}\leq\rho$. Then,

$H_{q}(B_{i,j}\mid Z_{i})\leq h_{q,\ell}(\rho^{\prime}_{j})\leq
h_{q,\ell}(\rho).$

Consequently, $H_{q}(\tau)\leq b\cdot h_{q,\ell}(\rho)+\ell$, establishing the
claim. ∎

###### Proof of Proposition 6.9.

Let $\mathcal{P}$ denote the property consisting of codes over
${\mathbb{F}}_{q}^{n}$ that are not $\left(\rho,\ell,L\right)\text{-list-
recoverable}$. Let $\tau\in\mathcal{T}_{\mathcal{P}}$ and let
$A\in\mathcal{M}_{n,\tau}$ be a matrix in ${\mathbb{F}}_{q}^{n\times a}$
($a\in\mathbb{N}$). By Observation 6.8, $A$ is
$\left(\rho,\ell,L+1\right)\text{-recovery-span-clustered}$. Let $W$ be a
$(\rho,\ell)$-recovery-clustered set of size $L+1$, contained in the column-
span of $A$. Note that $W$ must contain a linearly-independent subset $U$ of
size $b:=\lceil\log_{q}|W|\rceil=\lceil\log_{q}(L+1)\rceil$. Let
$D\in{\mathbb{F}}_{q}^{a\times b}$ such that $B:=AD$ is the matrix whose
columns are the elements of $U$, and note that $U$ is also
$\left(\rho,\ell\right)\text{-recovery-clustered}$. Let
$\tau^{\prime}={\mathsf{Emp}_{B}}$. By 6.10, $H_{q}(\tau^{\prime})\leq b\cdot
h_{q,\ell}(\rho)+\ell$. Furthermore, we can express $\tau^{\prime}$ as the
distribution of the random vector $xD$, where $x\sim\tau$. Consequently,
$\tau^{\prime}\in\mathcal{I}_{\tau}$. Therefore,

$\max_{\tau^{\prime\prime}\in\mathcal{I}_{\tau}}\left(1-\frac{H_{q}(\tau^{\prime\prime})}{\dim(\tau^{\prime})}\right)\geq
1-\frac{H_{q}(\tau^{\prime})}{b}\geq 1-h_{q,\ell}(\rho)-\frac{\ell}{b}.$

The claim now follows by Footnote 12. ∎

We note that the above derivation of Proposition 6.9 could also be achieved
via more standard arguments, which do not require Footnote 12. The actual
power Footnote 12 is that it enables reductions from other random code models
to the RLC model, as demonstrated in the proof of Theorems 1 and 4, via Lemma
6.12. This sort of argument involves an application of Footnote 12 in _its
less intuitive direction_ : rather than starting from an upper bound on
$H_{q}(\tau)$ for some set of distributions and using Footnote 12 to obtain a
lower bound on ${\mathrm{RLC}}(\mathcal{P})$, we start from some known lower
bound on ${\mathrm{RLC}}(\mathcal{P})$ and use the theorem to get an upper
bound on the entropy of certain “bad distributions.” The latter entropy bound
is then typically used in a union-bound argument to obtain a lower bound on
the threshold rate for some non-RLC model. This type of argument was used in
[MRRSW20] to prove that _Gallager LDPC codes_ are as list-decodable (and list-
recoverable) as RLCs.

######  Remark 6.11 (Average versions of list-decodability and list-
recoverability).

Average-radius list-decodability is a stronger property where we demand that
for every $L+1$ codewords their average distance to any center exceeds $\rho$
(as opposed to maximum distance for list-decodability). A code not being
$(\rho,L)$-average-radius list-decodable is also an $(L+1)$-local, row-
symmetric and scalar-invariant property.

For list-recovery, we can define a stronger variant where in Definition 6.7 we
allow input sets $Z_{i}$ such that the average size $|Z_{i}|$ over all
$i\in[n]$ is at most $\ell$. A violation of this stronger property is also a
local, row-symmetric and scalar-invariant property.

The generality of our framework thus means that we can get results for these
variants also automatically. We note that certain results for list-
decodability for RLCs, e.g., [GHK11, LW21], do not extend to average-radius
list-decoding (or list-recovery).

###  6.4 Proof of Theorems 1 and 4

We are now ready to prove Theorems 1 and 4. Our proofs take advantage of
Footnote 12 via the following lemma.

######  Lemma 6.12 (A generic reduction to random linear codes).

Let $n\in\mathbb{N}$, $q$ a prime power and $b\in\mathbb{N}$ such that
$\frac{n}{\log_{q}n}\geq\omega_{n\to\infty}\left(q^{2b}\right)$. Let
$\mathcal{C}\in{\mathbb{F}}_{q}^{n}$ be a linear code of rate $R\in[0,1]$,
sampled at random from some ensemble. Suppose that, for every $1\leq a\leq b$,
every distribution $\tau$ over ${\mathbb{F}}_{q}^{a}$ and every matrix
$B\in{\mathbb{F}}_{q}^{Rn\times a}$ with $\operatorname{rank}B=a$, we have

$\mathbb{E}_{\mathcal{C}}\left[\left|\left\\{A\in\mathcal{M}_{n,\tau}\mid
A\subseteq\mathcal{C}\right\\}\right|\right]\leq
q^{(H_{q}(\tau)-a(1-R)+a\varepsilon)n}\enspace,$ (24)

for some fixed $\varepsilon>0$. Then, for any row-symmetric and $b$-local
property $\mathcal{P}$ over ${\mathbb{F}}_{q}^{n}$ such that
$R\leq{\mathrm{RLC}}(\mathcal{P})-2\varepsilon$, it holds that

$\Pr_{\mathcal{C}}\left[\mathcal{C}\text{ satisfies }\mathcal{P}\right]\leq
q^{-n\left(\varepsilon-o_{n\to\infty}(1)\right)}\enspace.$

###### Proof.

Let $\tau\in\mathcal{T}_{\mathcal{P}}$. By Footnote 12, there is some
distribution $\tau^{\prime}\in\mathcal{T}_{\mathcal{P}}$ over
${\mathbb{F}}_{q}^{a}$ (where $1\leq a\leq b$) such that

$\frac{H_{q}(\tau^{\prime})}{a}\leq
1-{\mathrm{RLC}}(\mathcal{P})+o_{n\to\infty}(1)\enspace.$

Now, by Observation 6.5, followed by Markov’s bound,

$\displaystyle\mathrm{Pr}\left[\exists
A\in\mathcal{M}_{n,\tau}~{}~{}A\subseteq\mathcal{C}\right]$
$\displaystyle\leq\mathrm{Pr}\left[\exists
A\in\mathcal{M}_{n,\tau^{\prime}}~{}~{}A\subseteq\mathcal{C}\right]\leq\mathbb{E}\left[\left|\left\\{A\in\mathcal{M}_{n,\tau^{\prime}}\mid
A\subseteq\mathcal{C}\right\\}\right|\right]$
$\displaystyle\leq\mathrm{exp}_{q}\left(\left(H_{q}(\tau^{\prime})-a(1-R)+a\varepsilon\right)n\right)$
$\displaystyle\leq\mathrm{exp}_{q}\left(an\left(R-{\mathrm{RLC}}(\mathcal{P})+\varepsilon+o_{n\to\infty}(1)\right)\right)$
$\displaystyle\leq\mathrm{exp}_{q}\left(-na(\varepsilon-
o_{n\to\infty}(1))\right)\enspace.$

Therefore, by 6.3,

$\displaystyle\mathrm{Pr}\left[\mathcal{C}\text{ satisfies
}\mathcal{P}\right]$
$\displaystyle\leq\sum_{\tau\in\mathcal{T}_{\mathcal{P}}}\mathrm{Pr}\left[\exists
A\in\mathcal{M}_{n,\tau}~{}~{}A\subseteq\mathcal{C}\right]\leq\left|\mathcal{T}_{\mathcal{P}}\right|q^{-n(\varepsilon-
o_{n\to\infty}(1))}$ $\displaystyle\leq(n+1)^{q^{b}}q^{-n(\varepsilon-
o_{n\to\infty}(1))}\leq q^{-n(\varepsilon-o_{n\to\infty}(1))}\enspace.\qed$

We turn to proving the theorems.

###### Proof of Theorem 4.

Let $\tau$ be a distribution over ${\mathbb{F}}_{q}^{a}$, where $a\leq b$. By
Lemma 5.6,

$\displaystyle\mathbb{E}_{\mathcal{C}}\left[\left|\left\\{A\in\mathcal{M}_{n,\tau}\mid
A\subseteq\Lambda\mathcal{C}\right\\}\right|\right]$
$\displaystyle\leq\mathrm{exp}_{q}\left(n\cdot\left(H_{q}(\tau)-(1-R)a+\log_{q}\left(1+\eta
q^{a}\right)+\log_{q}2\right)\right)$
$\displaystyle\leq\mathrm{exp}_{q}\left(n\cdot\left(H_{q}(\tau)-(1-R)a+2\log_{q}2\right)\right)$
$\displaystyle\leq\mathrm{exp}_{q}\left(n\cdot\left(H_{q}(\tau)-(1-R)a+\varepsilon\right)\right)$
$\displaystyle\leq\mathrm{exp}_{q}\left(n\cdot\left(H_{q}(\tau)-(1-R)a+a\varepsilon\right)\right)\enspace,$

where $\Lambda\sim\mathsf{U}(\Gamma_{n})$. By Lemma 6.12, $\Lambda\mathcal{C}$
satisfies $\mathcal{P}$ with probability at most $q^{-n(\varepsilon-
o_{n\to\infty}(1))}$. Since $\mathcal{P}$ is scalar-invariant, the same holds
for $\mathcal{C}$. ∎

Theorem 1 requires the following lemma, which is analogous to Lemma 5.6.

######  Lemma 6.13 (Puncturings of low-bias codes are locally similar to
random linear codes).

Fix $b\in\mathbb{N}$ and a full-rank distribution $\tau$ over
${\mathbb{F}}_{q}^{b}$. Let $\mathcal{D}\subseteq{\mathbb{F}}_{q}^{m}$ be an
$\eta$-biased linear code ($\eta\geq 0$). Let $\varphi$ be a random ($m\to n$)
puncturing map. Denote $R=\frac{\log_{q}|\mathcal{D}|}{n}$. Then,

$\mathbb{E}_{\mathcal{C}}\left[\left|\left\\{A\in\mathcal{M}_{n,\tau}\mid
A\subseteq\mathcal{C}\right\\}\right|\right]\leq\mathrm{exp}_{q}\left(n\cdot\left(H_{q}(\tau)-(1-R)b+\log_{q}\left(1+\eta
q^{b}\right)\right)\right)$

###### Proof.

Let $\tau$ be a full-rank distribution over ${\mathbb{F}}_{q}^{b}$. Item 1 of
Lemma 5.9 yields B

$\mathbb{E}_{x\sim{\mathsf{Emp}_{B}}}\left[\tau(x)\right]\leq
q^{-b}\left(1+q^{b}\eta\right)\enspace,$

for all $B\in{\mathbb{F}}_{q}^{m\times b}$ such that $\operatorname{rank}B=b$
and $B\subseteq\mathcal{D}$. By Lemma 5.10,

$\mathrm{Pr}\left[\varphi(B)\in\mathcal{M}_{n,\tau}\right]\leq\mathrm{exp}_{q}\left(n\left(-b+H_{q}(\tau)+\log_{q}\left(1+q^{b}\eta\right)\right)\right)\enspace.$

The claim now follows by the union bound over the $\leq q^{Rnb}$ choices of
$B$. ∎

###### Proof of Theorem 1.

Let $\tau$ be a distribution over ${\mathbb{F}}_{q}^{a}$ with $a\leq b$. Lemma
6.13 yields

$\displaystyle\mathbb{E}_{\mathcal{C}}\left[\left|\left\\{A\in\mathcal{M}_{n,\tau}\mid
A\subseteq\mathcal{C}\right\\}\right|\right]$
$\displaystyle\leq\mathrm{exp}_{q}\left(n\cdot\left(H_{q}(\tau)-(1-R)a+\log_{q}\left(1+\eta
q^{a}\right)\right)\right)$
$\displaystyle\leq\mathrm{exp}_{q}\left(n\cdot\left(H_{q}(\tau)-(1-R)a+\frac{\eta
q^{a}}{\ln q}\right)\right)$
$\displaystyle=\mathrm{exp}_{q}\left({n\cdot\left(H_{q}(\tau)-(1-R)a+\frac{\varepsilon
b}{q^{b-a}}\right)}\right)$
$\displaystyle\leq\mathrm{exp}_{q}\left({n\cdot\left(H_{q}(\tau)-(1-R)a+a\varepsilon\right)}\right)\enspace,$

which implies the claim by virtue of Lemma 6.12. ∎

######  Remark 6.14 (On the conditions in Theorems 1 and 4, and comparison to
Theorem 5).

In the above proof of Theorems 1 and 4, as in the proof of Theorem 5, the core
of the proof is obtaining an upper bound on terms of the form
$\mathbb{E}\left[\left|\left\\{A\in\mathcal{M}_{n,\tau}\mid
A\subseteq\Lambda\mathcal{C}\right\\}\right|\right]$ for certain distributions
$\tau$, where $\mathcal{C}$ is a random puncturing of a mother code
$\mathcal{D}$.

When our assumption about $\mathcal{D}$ is that of near-optimal distance, we
bound this expectation via Lemma 5.6, which includes a bothersome $\log_{q}2$
term. This term needs to be bounded from above by $a\varepsilon$. One way to
overcome this term is to take $q$ large enough to make $\log_{q}2$ negligibly
small, as we do in Theorem 4. In Theorem 5 where we use [GHK11], the problem
is handled differently: Corollary 5.5 provides us with a “slack” that
dominates the $\log_{q}2$ term whenever $a$ is small, whereas for large $a$
the $a\varepsilon$ upper bound is not too restrictive. Finally, in Theorem 1
we avoid the bothersome term altogether via Lemma 6.13, due to our assumption
that $\mathcal{D}$ has small bias.

##  7 Derandomization of RLCs

In this section we prove Theorem 3, restated here. See 3

###### Proof.

Fix a property $\mathcal{P}\in\mathcal{K}$. Fix $\eta=\frac{\varepsilon b\ln
2}{2^{b}}$. Let $\mathcal{D}\subseteq{\mathbb{F}}_{2}^{m}$ be an $\eta$-biased
linear code of dimension $Rn$, where $m\leq O(n\cdot\eta^{-c})$ for some
universal $c\geq 2$. Explicit constructions of such a code $\mathcal{D}$ are
given in [ABNNR92, Ta-17]. We also assume that

$m\geq\frac{n}{1-2^{-\frac{\varepsilon}{2}}}\enspace,$ (25)

noting that $\frac{m}{n}$ can be taken to be as large as desired.

Sample a random increasing sequence of $n$ integers $1\leq
i_{1}<i_{2}<\dots<i_{n}\leq m$ uniformly from among all such sequences. Note
that such a sequence can be encoded by

$\log_{2}\binom{m}{n}+O(1)\leq n\left(\log_{2}\frac{m}{n}+O(1)\right)\leq
O\left(n\left(b+\log_{2}\frac{1}{\varepsilon}\right)\right)$

random bits, whose decoding can be done in $\mathrm{poly}(m)$ time.

Let $\mathcal{C}$ be the code defined by the random sequence
$i_{1},\dots,i_{n}$ via $\mathcal{C}=\left\\{\left(u_{i_{1}}\dotsc
u_{i_{n}}\right)\mid u\in\mathcal{D}\right\\}\subseteq{\mathbb{F}}_{2}^{n}$.
Clearly, a generating matrix for $\mathcal{C}$ can be obtained from that of
$\mathcal{D}$ in $\mathrm{poly}(m)=\mathrm{poly}(n)$ time. Hence, to prove the
theorem it suffices to show that $\mathcal{C}$ satisfies Eq. 4. Let
$\mathcal{C}^{\prime}\subseteq{\mathbb{F}}_{2}^{n}$ be a random $n$-puncturing
of $\mathcal{D}$. Let $T$ be the event that $\mathcal{C}^{\prime}$ satisfies
$\mathcal{P}$. Let $J$ denote the event that no coordinate of $\mathcal{D}$ is
sampled more than once for inclusion in $\mathcal{C}^{\prime}$. Note that
$\mathrm{Pr}\left[J\right]\geq\left(1-\frac{n}{m}\right)^{n}$. By Theorem 1,
$\mathrm{Pr}\left[T\right]\leq 2^{-(\varepsilon-o(1))n}$. Thus,

$\mathrm{Pr}\left[T\mid
J\right]\leq\frac{\mathrm{Pr}\left[T\right]}{\mathrm{Pr}\left[J\right]}\leq\mathrm{exp}_{2}\left(\left(-\varepsilon-\log_{2}\left(1-\frac{n}{m}\right)+o(1)\right)n\right)\leq
2^{-\Omega(\varepsilon n)}\enspace,$

where the last inequality follows from Eq. 25.

By row-symmetry, $\mathcal{P}$ is invariant to coordinate permutations of
$\mathcal{C}$. Observe that a uniformly random coordinate permutation of
$\mathcal{C}$ yields a code distributed identically to the distribution of
$\mathcal{C}^{\prime}$ conditioned on the event $J$. Therefore,

$\mathrm{Pr}\left[\mathcal{C}\text{ satisfies
}\mathcal{P}\right]=\mathrm{Pr}\left[T\mid J\right]\leq 2^{-\Omega(\varepsilon
n)}\enspace$ (26)

for every $\mathcal{P}\in\mathcal{K}$.

It remains to show that Eq. 26 implies Eq. 4. Let
$\mathcal{K}^{\prime}=\left(\mathcal{P}\in\mathcal{K}\mid\left|\mathcal{T}_{\mathcal{P}}\right|=1\right)$
(recall 6.3 for the definition of $\mathcal{T}_{\mathcal{P}}$). Observe that a
necessary condition for the event in Eq. 4 is that $\mathcal{C}$ satisfies
some property in $\mathcal{K}^{\prime}$. Indeed, suppose that $\mathcal{C}$
satisfies a property $\mathcal{P}\in\mathcal{K}$ and let
$\tau\in\mathcal{T}_{\mathcal{P}}$ such that $\mathcal{C}$ contains a matrix
in $\mathcal{M}_{n,\tau}$. Let $\mathcal{P}^{\prime}$ denote the $b$-local,
row-symmetric and monotone-increasing property for which
$\mathcal{T}_{\mathcal{P}^{\prime}}=\\{\tau\\}$. Clearly, $\mathcal{C}$
satisfies $\mathcal{P}^{\prime}$. Since $\mathcal{P}^{\prime}$ implies
$\mathcal{P}$, we have
${\mathrm{RLC}}(\mathcal{P}^{\prime})\geq{\mathrm{RLC}}(\mathcal{P})\geq
R^{*}$ and so $\mathcal{P}^{\prime}\in\mathcal{K}^{\prime}$. Thus, to prove
the theorem, it suffices to show that

$\mathrm{Pr}\left[\mathcal{C}\text{ satisfies some property
}\mathcal{P}^{\prime}\in\mathcal{K}^{\prime}\right]\leq 2^{-\Omega(\varepsilon
n)}\enspace.$ (27)

Now, by 4.10, $\left|\mathcal{K}^{\prime}\right|\leq(n+1)^{2^{b}}\leq
2^{o(n)}$. Thus, Eq. 27 follows from Eq. 26 by a union bound on
$\mathcal{K}^{\prime}$, noting that
$\mathcal{K}^{\prime}\subseteq\mathcal{K}$. ∎

##  8 Random puncturings of low-bias codes achieve capacity versus memoryless
additive noise

Here we prove Theorem 6. See 6 We require the following lemma.

######  Lemma 8.1.

Let $C\subseteq{\mathbb{F}}_{q}^{n}$ be a random rate $R$ puncturing of an
$\eta$-biased linear code. Fix $x\in{\mathbb{F}}_{q}^{n}\setminus\\{0\\}$.
Then,

$\Pr_{\mathcal{C}}\left[x\in\mathcal{C}\right]\leq
q^{n\cdot\left(-1+R+(q-1)\eta\right)}\enspace.$

###### Proof.

Denote the mother code by $\mathcal{D}\subseteq{\mathbb{F}}_{q}^{m}$ and let
$\varphi:{\mathbb{F}}_{q}^{m}\to{\mathbb{F}}_{q}^{n}$ be the puncturing map.
By the union bound,

$\displaystyle\mathrm{Pr}\left[x\in\mathcal{C}\right]$
$\displaystyle\leq\sum_{u\in\mathcal{D}}\mathrm{Pr}\left[\varphi(u)=x\right]=\sum_{u\in\mathcal{D}\setminus\\{0\\}}\prod_{i=1}^{n}\mathrm{Pr}\left[\varphi_{i}(u)=x_{i}\right]$
$\displaystyle=\sum_{u\in\mathcal{D}\setminus\\{0\\}}\prod_{i=1}^{n}\frac{\left|\left\\{j\in[m]\mid
u_{j}=x_{i}\right\\}\right|}{m}$
$\displaystyle\leq\sum_{u\in\mathcal{D}\setminus\\{0\\}}\prod_{i=1}^{n}\left(1-\frac{q-1}{q}(1-\eta)\right)$
(by Lemma 4.12)
$\displaystyle=\sum_{u\in\mathcal{D}\setminus\\{0\\}}\left(\frac{1+(q-1)\eta}{q}\right)^{n}$
$\displaystyle\leq q^{Rn}\left(\frac{1+(q-1)\eta}{q}\right)^{n}\leq
q^{n\cdot\left(-1+R+(q-1)\eta\right)}\ .{\hfill\qed}$

###### Proof of Theorem 6.

Let $J$ denote the event that our code $\mathcal{C}$ is MLDU-decodable with
error probability at most $2q^{-c_{\nu}\varepsilon^{2}n}$ with regard to the
$\nu$-memoryless additive noise channel (where $c_{\nu}>0$ shall be chosen
later). In other words, $J$ means that Eq. 6 holds for all $x\in\mathcal{C}$.
By linearity of $\mathcal{C}$, a sufficient condition for the latter is that
Eq. 6 holds for $x=0$. By the definition of the MLDU, the codeword $0$ with
noise vector $z$ is decoded correctly whenever $\nu(z)>\nu(z-x)$ for all
$x\in\mathcal{C}\setminus\\{0\\}$. Thus,

$\text{The code $\mathcal{C}$ satisfies $J$
}\quad\text{if}\quad\Pr_{z\sim\nu^{n}}\left[\forall
x\in\mathcal{C}\setminus\\{0\\}~{}~{}\nu(z)>\nu(z-x)\right]\geq
1-2q^{-c_{\nu}\varepsilon^{2}n}\enspace.$ (28)

Let $z\sim\nu^{n}$ and let $M_{z}$ denote the event that $z$ belongs to an
$\frac{\varepsilon}{3}$-typical-set, namely,
$q^{-H_{q}(\nu)n-\frac{\varepsilon n}{3}}\leq\nu(z)\leq
q^{-H_{q}(\nu)n+\frac{\varepsilon n}{3}}$. It is well known (e.g., [YM12])
that

$\Pr_{z\sim\nu^{n}}\left[M_{z}\right]\geq
1-q^{-c^{\prime}_{\nu}\varepsilon^{2}n}\enspace,$

for some positive constant $c^{\prime}_{\nu}$.

Denote
$E_{z}=\left\\{x\in{\mathbb{F}}_{q}^{n}\setminus\\{0\\}\mid\nu(z)\leq\nu(z-x)\right\\}$.
Since
$\sum_{x\in{\mathbb{F}}_{q}^{n}}\nu(z-x)=\sum_{x\in{\mathbb{F}}_{q}^{n}}\nu(x)=1$,
we have $|E_{z}|\leq\frac{1}{\nu(z)}$. Now, for a fixed code $\mathcal{C}$,

$\displaystyle{\Pr_{z\sim\nu^{n}}\left[\exists
x\in\mathcal{C}\setminus\\{0\\}~{}~{}\nu(z)\leq\nu(z-x)\right]}$
$\displaystyle={\Pr_{z\sim\nu^{n}}\left[E_{z}\cap\mathcal{C}\neq\emptyset\right]}$
$\displaystyle\leq{\Pr_{z\sim\nu^{n}}\left[E_{z}\cap\mathcal{C}\neq\emptyset\mid
M_{z}\right]+\Pr_{z\sim\nu^{n}}\left[\overline{M_{z}}\right]}$
$\displaystyle\leq{\Pr_{z\sim\nu^{n}}\left[E_{z}\cap\mathcal{C}\neq\emptyset\mid
M_{z}\right]+q^{-c^{\prime}_{\nu}\varepsilon^{2}n}}\enspace.$ (29)

Let $\eta=\frac{\varepsilon}{3(q-1)}$. By Lemma 8.1, for any $z$ such that
$M_{z}$ holds, we have

$\displaystyle\Pr_{\mathcal{C}}\left[E_{z}\cap\mathcal{C}\neq\emptyset\right]$
$\displaystyle\leq\sum_{x\in
E_{z}}\Pr_{\mathcal{C}}\left[x\in\mathcal{C}\right]$
$\displaystyle\leq\sum_{x\in
E_{z}}q^{n\cdot\left(-1+R+(q-1)\eta\right)}\leq|E_{z}|\cdot
q^{n\cdot\left(-1+R+(q-1)\eta\right)}$ $\displaystyle\leq\frac{1}{\nu(z)}\cdot
q^{n\cdot\left(-1+R+(q-1)\eta\right)}$ $\displaystyle\leq
q^{n\cdot\left(-1+R+(q-1)\eta+H_{q}(\nu)+\frac{\varepsilon}{3}\right)}$
$\displaystyle\leq q^{-\frac{\varepsilon n}{3}}\enspace.$ (30)

Now,

$\displaystyle\Pr_{\mathcal{C}}\left[\mathcal{C}\text{ does not satisfy
}J\right]$ $\displaystyle\leq\
\Pr_{\mathcal{C}}\left[\Pr_{z\sim\nu^{n}}\left[\forall
x\in\mathcal{C}\setminus\\{0\\}~{}~{}\nu(z)>\nu(z-x)\right]<1-2q^{-c_{\nu}\varepsilon^{2}n}\right]$
$\displaystyle(\text{by \lx@cref{creftype~refnum}{eq:StochasticProof1}}$
$\displaystyle=\ \Pr_{\mathcal{C}}\left[\Pr_{z\sim\nu^{n}}\left[\exists
x\in\mathcal{C}\setminus\\{0\\}~{}~{}\nu(z)\leq\nu(z-x)\right]\geq
2q^{-c_{\nu}\varepsilon^{2}n}\right]$ $\displaystyle\leq\
\Pr_{\mathcal{C}}\left[\Pr_{z\sim\nu^{n}}\left[E_{z}\cap\mathcal{C}\neq\emptyset\mid
M_{z}\right]\geq
2q^{-c_{\nu}\varepsilon^{2}n}-q^{-c^{\prime}_{\nu}\varepsilon^{2}n}\right]$
$\displaystyle(\text{by \lx@cref{creftype~refnum}{eq:StochasticProof2}})$
$\displaystyle\leq\
\frac{\mathbb{E}_{\mathcal{C}}\left[\Pr_{z\sim\nu^{n}}\left[E_{z}\cap\mathcal{C}\neq\emptyset\mid
M_{z}\right]\right]}{2q^{-c_{\nu}\varepsilon^{2}n}-q^{-c^{\prime}_{\nu}\varepsilon^{2}n}}$
$\displaystyle(\text{by Markov's inequality})$ $\displaystyle\leq\
\frac{q^{-\frac{\varepsilon
n}{3}}}{2q^{-c_{\nu}\varepsilon^{2}n}-q^{-c^{\prime}_{\nu}\varepsilon^{2}n}}\enspace.$
$\displaystyle(\text{by \lx@cref{creftype~refnum}{eq:StochasticProof3}})$

Taking $c_{\nu}=\min\left\\{c_{\nu^{\prime}},\frac{1}{4}\right\\}$ makes the
right-hand side $q^{-\Omega_{\nu}(\varepsilon n)}$, finishing the proof. ∎

## Acknowledgments

The authors thank João Ribeiro for pointing out an improvement to Theorem 3,
and Zeyu Guo for finding an error in a previous version of this paper.

## References

  * [ABNNR92] Noga Alon, Jehoshua Bruck, Joseph Naor, Moni Naor and Ron M. Roth  “Construction of asymptotically good low-rate error-correcting codes through pseudo-random graphs”  In _IEEE Trans. Inf. Theory_ 38.2, 1992, pp. 509–516  DOI: 10.1109/18.119713
  * [CGV13] Mahdi Cheraghchi, Venkatesan Guruswami and Ameya Velingker  “Restricted Isometry of Fourier Matrices and List Decodability of Random Linear Codes”  In _SIAM J. Comput._ 42.5, 2013, pp. 1888–1914  DOI: 10.1137/120896773
  * [CT06] Thomas M. Cover and Joy A. Thomas  “Elements of information theory (2. ed.)”  Wiley, 2006  URL: http://www.elementsofinformationtheory.com/
  * [FKS20] Asaf Ferber, Matthew Kwan and Lisa Sauermann  “List-decodability with large radius for Reed-Solomon codes” To appear in FOCS 2021  In _CoRR_ abs/2012.10584, 2020  arXiv: https://arxiv.org/abs/2012.10584
  * [GHK11] Venkatesan Guruswami, Johan Håstad and Swastik Kopparty  “On the List-Decodability of Random Linear Codes”  In _IEEE Trans. Inf. Theory_ 57.2, 2011, pp. 718–725  DOI: 10.1109/TIT.2010.2095170
  * [GLMRSW20] Venkatesan Guruswami, Ray Li, Jonathan Mosheiff, Nicolas Resch, Shashwat Silas and Mary Wootters  “Bounds for List-Decoding and List-Recovery of Random Linear Codes”  In _Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX/RANDOM 2020, August 17-19, 2020, Virtual Conference_ 176, LIPIcs  Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020, pp. 9:1–9:21  DOI: 10.4230/LIPIcs.APPROX/RANDOM.2020.9
  * [GLSTW20] Zeyu Guo, Ray Li, Chong Shangguan, Itzhak Tamo and Mary Wootters  “Improved List-Decodability of Reed-Solomon Codes via Tree Packings” To appear in FOCS 2021  In _CoRR_ abs/2011.04453, 2020  arXiv: https://arxiv.org/abs/2011.04453
  * [GMRSW21] Venkatesan Guruswami, Jonathan Mosheiff, Nicolas Resch, Shashwat Silas and Mary Wootters  “Sharp Threshold Rates for Random Codes”  In _12th Innovations in Theoretical Computer Science Conference, ITCS 2021, January 6-8, 2021, Virtual Conference_ 185, LIPIcs  Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2021, pp. 5:1–5:20  DOI: 10.4230/LIPIcs.ITCS.2021.5
  * [GN14] Venkatesan Guruswami and Srivatsan Narayanan  “Combinatorial Limitations of Average-Radius List-Decoding”  In _IEEE Trans. Inf. Theory_ 60.10, 2014, pp. 5827–5842  DOI: 10.1109/TIT.2014.2343224
  * [Gol11] Oded Goldreich  “Three XOR-Lemmas - An Exposition”  In _Studies in Complexity and Cryptography. Miscellanea on the Interplay between Randomness and Computation_ 6650, Lecture Notes in Computer Science  Springer, 2011, pp. 248–272  DOI: 10.1007/978-3-642-22670-0“˙22
  * [GR11] Venkatesan Guruswami and Atri Rudra  “Soft Decoding, Dual BCH Codes, and Better List-Decodable varepsilon-Biased Codes”  In _IEEE Trans. Inf. Theory_ 57.2, 2011, pp. 705–717  DOI: 10.1109/TIT.2010.2095193
  * [GRS] Venkatesan Guruswami, Atri Rudra and Madhu Sudan  “Essential coding theory” Draft available at http://cse.buffalo.edu/faculty/atri/courses/coding-theory/book/
  * [GS99] Venkatesan Guruswami and Madhu Sudan  “Improved decoding of Reed-Solomon and algebraic-geometry codes”  In _IEEE Trans. Inf. Theory_ 45.6, 1999, pp. 1757–1767  DOI: 10.1109/18.782097
  * [GST21] Eitan Goldberg, Chong Shangguan and Itzhak Tamo  “List-decoding and list-recovery of Reed-Solomon codes beyond the Johnson radius for any rate”  In _CoRR_ abs/2105.14754, 2021  arXiv: https://arxiv.org/abs/2105.14754
  * [Gur06] Venkatesan Guruswami  “Algorithmic Results in List Decoding”  In _Found. Trends Theor. Comput. Sci._ 2.2, 2006  DOI: 10.1561/0400000007
  * [LW21] Ray Li and Mary Wootters  “Improved List-Decodability of Random Linear Binary Codes”  In _IEEE Trans. Inf. Theory_ 67.3, 2021, pp. 1522–1536  DOI: 10.1109/TIT.2020.3041650
  * [MRRSW20] Jonathan Mosheiff, Nicolas Resch, Noga Ron-Zewi, Shashwat Silas and Mary Wootters  “LDPC Codes Achieve List Decoding Capacity”  In _61st IEEE Annual Symposium on Foundations of Computer Science, FOCS 2020, Durham, NC, USA, November 16-19, 2020_ IEEE, 2020, pp. 458–469  DOI: 10.1109/FOCS46700.2020.00050
  * [Res20] Nicolas Resch  “List-Decodable Codes: (Randomized) Constructions and Applications”, 2020  URL: http://reports-archive.adm.cs.cmu.edu/anon/2020/CMU-CS-20-113.pdf
  * [RW14] Atri Rudra and Mary Wootters  “Every list-decodable code for high noise has abundant near-optimal rate puncturings”  In _Symposium on Theory of Computing, STOC 2014, New York, NY, USA, May 31 - June 03, 2014_ ACM, 2014, pp. 764–773  DOI: 10.1145/2591796.2591797
  * [RW14a] Atri Rudra and Mary Wootters  “It’ll probably work out: improved list-decoding through random operations”  In _Electronic Colloquium on Computational Complexity (ECCC)_ 21, 2014, pp. 104  URL: http://eccc.hpi-web.de/report/2014/104
  * [RW18] Atri Rudra and Mary Wootters  “Average-radius list-recovery of random linear codes”  In _Proceedings of the 2018 ACM-SIAM Symposium on Discrete Algorithms, SODA_ , 2018
  * [ST20] Chong Shangguan and Itzhak Tamo  “Combinatorial list-decoding of Reed-Solomon codes beyond the Johnson radius”  In _Proccedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, STOC 2020, Chicago, IL, USA, June 22-26, 2020_ ACM, 2020, pp. 538–551  DOI: 10.1145/3357713.3384295
  * [Ta-17] Amnon Ta-Shma  “Explicit, almost optimal, epsilon-balanced codes”  In _Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2017, Montreal, QC, Canada, June 19-23, 2017_ ACM, 2017, pp. 238–251  DOI: 10.1145/3055399.3055408
  * [Woo13] Mary Wootters  “On the list decodability of random linear codes with large error rates”  In _Symposium on Theory of Computing Conference, STOC’13, Palo Alto, CA, USA, June 1-4, 2013_ , 2013, pp. 853–860  DOI: 10.1145/2488608.2488716
  * [YM12] En-Hui Yang and Jin Meng  “Non-asymptotic equipartition properties for independent and identically distributed sources”  In _2012 Information Theory and Applications Workshop_ , 2012, pp. 39–46  DOI: 10.1109/ITA.2012.6181822
  * [ZP81] Victor Vasilievich Zyablov and Mark Semenovich Pinsker  “List Concatenated Decoding”  In _Problemy Peredachi Informatsii_ 17.4 Russian Academy of Sciences, Branch of Informatics, Computer EquipmentAutomatization, 1981, pp. 29–33