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$.

$L$	$\Omega_L'$
2	$(\tfrac{1}{2},\tfrac{1}{2})$
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 bit string $T\in\{0,1\}^L$ in the definition of a signature is encoded as $T\in\{1,-1\}^L$, after the substitution $0\mapsto 1$ and $1\mapsto -1$.
• We need only consider those $T$ for which $T_1=1$ because of $S_{\omega}(T)=-S_{\omega}(-T)$.

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)