Tight Bounds on List-Decodable and List-Recoverable Zero-Rate Codes

Since our focus is on zero-rate list-decodable/-recoverable codes, it helps to first review the proof of the zero-rate threshold $p_{\ast }(q,\mathrm{\ell },L)$. A lower bound can be easily obtained by a random construction that attains a positive rate for any $p\le p_{\ast }(q,\mathrm{\ell },L)-\epsilon$. For the upper bound, let us first consider the list-decoding case, i.e., $\mathrm{\ell }=1$. The proof in [5, 6, 25], at a high-level, proceeds via a double-counting argument.⁵⁵5A characterization of $p_{\ast }(q,1,L)$ was announced in [5, 6] whose proof was flawed. The work [25] filled in the gaps therein and characterized $p_{\ast }(q,\mathrm{\ell },L)$ for general $\mathrm{\ell }$. For any $(p,\mathrm{\ell },L)$-list-decodable code $𝒞\subset {[q]}^n$, the proof aims to upper and lower bound the radius of a list averaged over the choice of the list from $𝒞$:

Comparing the bounds produces an upper bound on $|𝒞|$. Here ${\mathrm{rad}}_{\mathrm{H}}(\cdot )$, known as the Chebyshev radius of a list, is the relative radius of the smallest Hamming ball containing all codewords in the list. A lower bound on Equation 1 essentially follows from list-decodability of $𝒞$. Indeed, each term (corresponding to lists consisting of distinct codewords) is lower bounded by $p$, otherwise a list that fits into a ball of radius at most $np$ is found, violating list-decodability of $𝒞$. Therefore Equation 1 is at least $p-o(1)$, where $o(1)$ is to account for lists with not-all-distinct codewords.

On the other hand, it is much more tricky to upper bound Equation 1 as, in general, ${\mathrm{rad}}_{\mathrm{H}}$ admits no analytically closed form and can only be computed by solving a min-max problem. Previous proofs [25] then first extracts a subcode ${𝒞}^{\prime }$ with highly-regular list structures via the hypergraph Ramsey’s theorem. This allows one to assert that all lists have essentially the same radius and all codewords in each list have essentially the same distance to the center of the list. As a result, the min-max expression is “linearized” and Equation 1 can be upper bounded when restricted to ${𝒞}^{\prime }$. The downside is that the Ramsey reduction step is rather lossy for code size.

The effect of the Ramsey reduction, put formally, is to enforce the average radius:

of every list in the subcode to be approximately equal. To extract the regularity structures in lists without resorting to extremal bounds from Ramsey theory, [1] introduced the notion of weighted average radius which “linearizes” the Chebyshev radius in a weighted manner:

where $\omega$ is a distribution on $L$ elements. For any weighting $\omega$, ${\overline{\mathrm{rad}}}_{\omega }$ of lists from the code forms a suite of succinct statistics of the list distribution. It turns out ${\overline{\mathrm{rad}}}_{U_L}=\overline{\mathrm{rad}}$ (where $U_L$ denotes the uniform distribution on $[L]$) is maximal under all $\omega$. Recall that the double-counting argument suggests that in an optimal zero-rate code, the behaviour of the ensemble average of $\mathrm{rad}$ is essentially captured by that of $\overline{\mathrm{rad}}$. In particular, list-decodability ensures that $\overline{\mathrm{rad}}$ of most lists should be large. However, not too many lists in an optimal code are expected to have large ${\overline{\mathrm{rad}}}_{\omega }$ for any $\omega \ne U_L$. [1] then managed to quantify the gap between $\overline{\mathrm{rad}}={\overline{\mathrm{rad}}}_{U_L}$ and ${\overline{\mathrm{rad}}}_{\omega }$ (with $\omega \ne U_L$), which yields improved (and sometimes optimal) size-radius trade-off of zero-rate codes.

Our major technical contribution is in extrapolating the above ideas to list-recovery. The challenge lies particularly in defining a proper notion of weighted average radius and proving its properties. Our definition relies crucially on an embedding $\phi$ from $[q]$ to the simplex in ${ℝ}^q$ and relaxes the center $𝒓$ of the list to be a fractional vector. Specifically, denoting by $\mathrm{\Delta }=\{𝒂\in {ℝ}_{\ge 0}^q:{\sum }_{i=1}^q{a}_i=1\}$ the simplex in ${ℝ}^q$ and $\partial \mathrm{\Delta }=\{{𝒆}_1,\mathrm{\cdots },{𝒆}_q\}$ its vertices (i.e., the standard basis of ${ℝ}^q$), we let the embedding $\phi$ map each symbol $x\in [q]$ to the standard basis vector ${𝒆}_x\in \partial \mathrm{\Delta }$. Denoting by ${𝒙}_1,\mathrm{\cdots },{𝒙}_L\in {(\partial \mathrm{\Delta })}^n$ the (element-wise) images of a list ${𝒄}_1,\mathrm{\cdots },{𝒄}_L\in {[q]}^n$, we define the weighted average radius of ${𝒙}_1,\mathrm{\cdots },{𝒙}_L$ as:

where $\omega$ is any distribution on $[L]$.

The notriviality and significance of the above notion, especially the embedding used therein, is three-fold.

• $\mathrm{■}$

  First, as the weighting $\omega$ varies, ${\overline{\mathrm{rad}}}_{\omega }$ serves as a bridge between the standard average radius in Equation 2 and the Chebyshev radius. Indeed, $\omega =U_L$ recovers the former, and the maximum ${\overline{\mathrm{rad}}}_{\omega }$ over $\omega$ recovers the latter. However, we caution that the second statement does not hold without the embedding since the Hamming distance between $q$-ary symbols per se is not and cannot be interpolated by a convex function, which makes the minimax theorem inapplicable. Fortunately, our embedding affinely extend the $q$-ary Hamming distance to the simplex therefore brings back the applicability of the minimax theorem and connects ${\max }_{\omega }{\overline{\mathrm{rad}}}_{\omega }$ to $\mathrm{rad}$.

• $\mathrm{■}$

  Second, our definition in Equation 3 allows $𝒚$ to take any value on the simplex, instead of only its vertices, i.e., the image of $[q]$ under $\phi$. Though embedding naively to the hypercube ${[0,1]}^q$ seems convenient, upon solving the expression with fractional $𝒚$ one does not necessarily obtain a notion that is guaranteed to closely approximate the original version with integral $𝒚$. In contrast, using linear programming duality, we show that our embedding yields relaxed notion of radius which closely approximates the actual Chebyshev radius. Indeed, upon rounding the fractional center $𝒚$ and taking its pre-image under $\phi$, our results guarantee that the resulting radius must have negligible difference from the Chebyshev radius. Precisely speaking, we want to find a vector $𝒚={(y(i,j))}_{[n]\times [q]}\in \mathrm{\Delta }$ close to the $L$ images of the codewords ${𝒙}_1,\mathrm{\dots },{𝒙}_L$ by linear programming. Meanwhile, we want $𝒚(i):=(y(i,1),\mathrm{\dots },y(i,q))$ to belong to $\partial \mathrm{\Delta }$ so that we can find a preimage of $𝒚(i)$ in $[q]$. Since $𝒚(i)\in \mathrm{\Delta }$, the components in $𝒚(i)$ are subject to ${\sum }_{j=1}^{q}y(i,j)=1$. This implies that at least one component of $𝒚(i)$ is nonzero. The basic feasible solution guarantees that there exists a feasible solution such that most of $y(i,j)$ are $0$. Combining with the fact ${\sum }_{j=1}^{q}y(i,j)=1$ forces $(y(i,1),\mathrm{\dots },y(i,q))\in \partial \mathrm{\Delta }$ for almost all $i\in [n]$. Thus, we obtain a negligible loss in the conversion between Hamming distance and Euclidean distance.

• $\mathrm{■}$

  Finally, under the embedding $\phi$, the weighted average radius ${\overline{\mathrm{rad}}}_{\omega }$ still retains the appealing feature that the minimization can be analytically solved, therefore giving rise to an explicit expression (see Equation 31) which greatly facilitates our analysis.

We then show, via techniques deviating from those in [1], three key properties that are required by the subsequent arguments.

1. 1.

   For any fixed distribution $P$, if entries of codewords in the list are generated i.i.d. using $P$, then

   $$f(P,\omega )≔\underset{(X_1,\mathrm{\cdots },X_L)\sim P^{\otimes L}}{𝔼}\left[1-\underset{x\in [q]}{\max }\sum _{\begin{array}{c}i\in [L]\\ X_i=x\end{array}}\omega (i)\right]$$

   is maximized when $\omega =U_L$. Moreover, the equality holds if and only if $\omega =U_L$ for $q\ge 3$ and any $L$. Our approach is different from [1] as we can not explicitly represent function $f(P,\omega )$.

2. 2.

   Furthermore, if entries of codewords in the list are generated i.i.d. using a certain $P$, then $f(P,U_L)$ is upper bounded by $f(P_{q,p},U_L)$ with $P_{q,p}=(\frac{1-p}{q},\mathrm{\dots },\frac{1-p}{q},p)$ and $p={\max }_{i\in [q]}P(i)$. This follows from the Schur convexity property proved in [25].

3. 3.

   Finally, denoting by $P_i$ the distribution of the $i$-th components of codewords in code $𝒞$, Schur convexity promises $f(P_i,U_L)\le f(P_{q,p_i},U_L)$. In [25], it is proved that $f(P_{q,p},U_L)$ is convex for $p\in [1/q,1]$. Thus, we can conclude that

   $$\frac{1}{n}\sum _{i\in [n]}f(P_i,U_L)\le f(P_{q,p},U_L)$$

   with $p=\frac{1}{n}{\sum }_{i\in [n]}{p}_i$.

The remaining part of our proof is similar to [1]. We show that a code $𝒞$ either has radius

or most of $L$-tuples with distinct codewords in $𝒞$ are distributed close to uniform,. For the former case, we use the convexity property to show that the list-decodability of $𝒞$ can not exceed $f(U_q,U_L)=p_{\ast }(q,L)$ by much. For the latter case, since most of $L$-tuples of distinct codewords in ${𝒞}^L$ looks uniformly at random, we can show that the list-decodablilty of $𝒞$ is very close to that of random codes which is $f(U_q,U_L)$.

For list-recovery, i.e., $\mathrm{\ell }>1$, we find an embedding ${\phi }_{\mathrm{\ell }}$ that maps each element in $[q]$ to a superposition of $\mathrm{\ell }$ vertices of the simplex in ${ℝ}^q$, i.e., we map the element in $[q]$ to a vector space ${[0,1]}^{𝒳}$ where $𝒳=\left(\genfrac{}{}{0pt}{}{[q]}{\mathrm{\ell }}\right)$ is the collection of all $\mathrm{\ell }$-subsets in $[q]$. Concretely, we define ${\phi }_{\mathrm{\ell }}(i):={\sum }_{A\in 𝒳,i\in A}{𝒆}_A$ where ${({𝒆}_A)}_{A\in 𝒳}$ is a standard basis of ${ℝ}^{𝒳}$. The intuition behind this map is that if $i\in X$, we have ${\Vert {\phi }_{\mathrm{\ell }}(i)-{𝒆}_X\Vert }_1=\left(\genfrac{}{}{0pt}{}{q}{\mathrm{\ell }}\right)-1$ and otherwise ${\Vert {\phi }_{\mathrm{\ell }}(i)-{𝒆}_X\Vert }_1=\left(\genfrac{}{}{0pt}{}{q}{\mathrm{\ell }}\right)+1$. Similar to the list decoding, given $L$ codewords in ${[q]}^n$, we obtain $L$ vectors ${𝒙}_1,\mathrm{\dots },{𝒙}_L$ under the map ${\phi }_{\mathrm{\ell }}$. Our goal is to find a vector $𝒚={(y(i,A))}_{[n]\times 𝒳}$ close to these $L$ vectors subject to the constraint that ${\sum }_{A\in 𝒳}y(i,A)=1$ for any $i\in [n]$. This constraint combined with the basic feasible solution argument forces that for almost all $i\in [n]$, ${(y(i,A))}_{A\in 𝒳}$ is of the form ${𝒆}_X$. For such $i$, we can find an $\mathrm{\ell }$-subset $X\in 𝒳$ preserving the distance, i.e.,

Besides the linear programming relaxation, further adjustments for the proof of properties analogous to Items 1, 2, and 3 above are required.

As alluded to before, a code that saturates the optimal size-radius trade-off should essentially saturate both the upper and lower bounds on the quantity

considered in the double-counting argument. Indeed, our impossibility result implies that any optimal zero-rate code must contain a large fraction of random-like $L$-tuples $({𝒄}_1,\mathrm{\dots },{𝒄}_L)$, i.e., for every $𝒖\in {[q]}^L$

where ${𝒄}_j=({𝒄}_j(1),\mathrm{\dots },{𝒄}_j(n))\in {[q]}^n$. To match such an impossibility result, an optimal construction should contain as many such $L$-tuples as possible. A simplex-like code then becomes a natural candidate. This is a natural extension of the construction in [1] to larger alphabet. An $M\times n$ codebook $𝒞$ consisting of $M$ codewords each of length $n$ is constructed by putting as columns all possible distinct length-$M$ vectors that contains identical numbers of $1,2,\mathrm{\cdots },q$. It is not hard to see by symmetry that (4) becomes equality for every $L$-tuple with distinct codewords in $𝒞$. Thus, $𝒞$ is the most regular code.

We also remark that, unlike for positive-rate codes, the prototypical random construction (with expurgation) does not lead to favorable size-radius trade-off since the deviation of random sampling is comparatively too large in the zero-rate regime. In contrast, the simplex code is deterministically regular and has no deviation.

Suppose $\mathrm{rad}({𝒙}_1,\mathrm{\cdots },{𝒙}_L)=t$. Then there exists $𝒚\in {\mathrm{\Delta }}^n$ such that for every $i\in [L]$,

where the first equality is by Equations 10 and 11. That is, the following polytope is nonempty:

Equivalently, the following linear program (LP) is feasible:

Since the equality $⟨𝒂,𝒚⟩\le b$ is equivalent to the equality $⟨𝒂,𝒚⟩+z=b,z\ge 0$, the above LP can be written in equational form:

or more compactly in matrix form:

Here $A\in {ℝ}^{L\times (nq)}$ and $B\in {ℝ}^{n\times (nq)}$ encode respectively the fourth and third constraints in Equation 25, and $I_L\in {ℝ}^{L\times L},{\mathrm{𝟏}}_L\in {ℝ}^L$ denote respectively the $L\times L$ identity matrix and the all-one vector of length $L$. It is clear that This implies that there exists a feasible solution $𝒚,𝒛$ that has at most $n+L$ nonzeros and thus $𝒚={(y(j,k))}_{(j,k)\in [n]\times [q]}$ has at most $n+L$ nonzeros. Indeed, such solutions are known as the basic feasible solutions. Note that for every block $j\in [n]$, ${\sum }_{k=1}^{q}y(j,k)=1$. This implies that $y(j,1),\mathrm{\dots },y(j,q)$ cannot be simultaneously $0$. Moreover, if $q-1$ out of them are $0$, the remaining one is forced to be $1$. Since there are $n$ blocks in total, by the pigeonhole principle, there are at least $n-L$ choices of $j\in [n]$ such that $𝒚(j)=(y(j,1),\mathrm{\dots },y(j,q))\in \partial \mathrm{\Delta }$. Without loss of generality, we assume that these $n-L$ indices are $1,\mathrm{\dots },n-L$. Let $𝒓\in {[q]}^n$ be such that $\phi (𝒓(j))=𝒚(j)$ for $j=1,\mathrm{\dots },n-L$ and $r(j)$ is any value in $[q]$ for $j=n-L+1,\mathrm{\dots },n$. Since $d({𝒙}_i(j),𝒚(j))\in [0,1]$ and $d_{\mathrm{H}}({𝒄}_i(j),𝒓(j))\in \{0,1\}$, the difference between $d({𝒙}_i,𝒚)$ and $d_{\mathrm{H}}({𝒄}_i,𝒓)$ is at most $L$. The proof is completed. $◀$

We further relax $\mathrm{rad}$ by defining the weighted average radius. For ${𝒙}_1,\mathrm{\cdots },{𝒙}_L\in {(\partial \mathrm{\Delta })}^n$ and $\omega \in \mathrm{\Delta }([L])$, let

In words, weighted average radius is obtained by replacing the maximization over $i\in [L]$ in the definition of relaxed radius (see Equation 12) with an average with respect to a distribution $\omega$.

Since the objective of the minimization is separable, one can minimize over each $y(j)$ individually and obtain an alternative expression. Suppose ${𝒙}_1,\mathrm{\cdots },{𝒙}_L\in {(\partial \mathrm{\Delta })}^n$ are the images of ${𝒄}_1,\mathrm{\cdots },{𝒄}_L\in {[q]}^n$ under the embedding $\phi$. Then

Equation 30 holds since the objective in brackets only depends on ${𝒚}_j$, not on other ${({𝒚}_{j^{\prime }})}_{j^{\prime }\in [n]\setminus \{j\}}$. To see Equation 31, we note that a maximizer ${𝒚}^{\ast }\in \mathrm{\Delta }$ to the following problem ${\max }_{𝒚\in \mathrm{\Delta }}{\sum }_{i\in [L]}\omega (i)y(x_i)$, where $\omega \in \mathrm{\Delta }([L])$ and $(x_1,\mathrm{\cdots },x_L)\in {[q]}^L$ are fixed, is given by ${𝒚}^{\ast }={𝒆}_{x^{\ast }}$ where $x^{\ast }\in [q]$ satisfies $x^{\ast }\in {argmax}_{x\in [q]}{\sum }_{i\in [L]}\omega (i)\mathrm{𝟙}\left\{x_i=x\right\}.$