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

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)