Code used in the paper “List-decodable zero-rate codes”

Let $w=(w^{(1)},\dotsc,w^{(L)})$ be an $L$-tuple of binary strings of length $n$. The radius of $w$ is $$\min_{y\in \{0,1\}^n} \max_i \lVert y-x^{(i)}\rVert.$$ It is very convenient to consider the linear relaxation of the radius, given by $$\rad\eqdef\min_{y\in [0,1]^n} \max_i \norm{y-x^{(i)}}.$$

For a measure $\omega$ on $[L]$, one can also define mean-radius $$\mrad_{\omega}(x)\eqdef \min_{y\in [0,1]^n} \E_{i\sim \omega} \norm{x^{(i)}-y}$$ Clearly, $\rad(x)\geq \mrad_{\omega}(x)$. In the paper, it is shown that $$\rad(x)=\max_{\omega\in\Omega_L'} \mrad_{\omega}(x)$$ for a certain finite set $\Omega_L'$. The paper also gives an algorithm to compute this set.

We implemented this algorithm. Here are the results of the computation for small $L$.

3$(\tfrac{1}{2},\tfrac{1}{2},0),(\tfrac{1}{2},0,\tfrac{1}{2}), (0,\tfrac{1}{2},\tfrac{1}{2})$
4$(\tfrac{1}{2},\tfrac{1}{2},0,0),(\tfrac{1}{4},\tfrac{1}{4},\tfrac{1}{4},\tfrac{1}{4})$ and permutations thereof
5$(\tfrac{1}{2},\tfrac{1}{2},0,0,0),(\tfrac{1}{4},\tfrac{1}{4},\tfrac{1}{4},\tfrac{1}{4},0),(\tfrac{1}{3},\tfrac{1}{6},\tfrac{1}{6},\tfrac{1}{6},\tfrac{1}{6})$ and permutations thereof
The code is a straightforward implementation of the algorithm in the paper, with the following changes, whose aim is to speed up the computation. The resulting Sage code (for $L=5$) is this:
import itertools
L  = 5
simplex = Polyhedron(vertices = [[(1 if i==j else 0) for j in range(L)] for i in range(L)])
Siterator  = itertools.product([1,-1], repeat=2^(L-1) ) # Iterate over tuples of 1,-1

allVertices = set()
for S in Siterator:
    Ts = itertools.product(* ([[1]]+[[-1,1]]*(L-1)))  # Iterator over L-tuples of 1,-1 starting with 1
    inequalities = [(0,)+tuple(el*S[idx] for el in T) for idx,T in enumerate(Ts)]
    OmegaS = simplex & Polyhedron(ieqs = inequalities)
    allVertices |= set(OmegaS.vertices())

allVertices -= set(simplex.vertices())
print "\n".join(str(x) for x in allVertices)

Back to the homepage