Amnon Ta-Shma: Parity samplers and explicit, epsilon-Balanced codes close to the GV Bound

Abstract:

I will show an explicit construction of a binary error correcting code with relative distance 1/2-epsilon and relative rate about epsilon^2. This comes close to the Gilbert-Varshamov bound
and the LP lower bound. Previous explicit constructions had rate about epsilon^3, and this is the first explicit construction to get
that close to the Gilbert-Varshamov bound.

Technically, we define Parity Samplers. A parity sampler is a collection of sets with the property
that for every "test" A of a given constant density, the probability a set from the collection falls into the test set

A an \emph{even} number of times is about half. A \emph{sparse} parity sampler immediately implies a good code with distance close to half. The complete t-complex of all sequences of cardinality t is a good parity sampler, but with too many sets in the collection. Rozenman and Wigderson, and independently Alon, used random walks over expanders to explicitly construct sparse parity samplers, and their construction implies explicit codes with relative rate epsilon^4.

I will show how one can get better explicit parity samplers (and therefore also better explicit codes)using a variant of the zig-zag product. In the random walk sampler, there exist many sets with substantial overlap. One way to look at
the zig-zag product is that it takes a sub-collection of the random walk sampler, and this sub-collection has a smaller overlap between
sets in the collection. The zig-zag product achieves that by keeping a small internal state. I will show that by enlarging the internal
state one can further reduce the overlap, and as a result improve the quality of the parity sampler.