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 theLP lower bound. Previous explicit constructions had rate aboutepsilon^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 setswith the property
that for every "test"A of a given constant density, the probability a setfrom 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 completet-complex of all sequences of cardinalityt is a good parity sampler, but with too many sets in the collection.Rozenman andWigderson, and independentlyAlon, used random walks over expanders to explicitly construct sparse parity samplers, and their construction implies explicit codes with relative rateepsilon^4.

I will show how one can get better explicit parity samplers (and therefore also better explicit codes) using a variant of thezig-zag product. In the random walk sampler, there exist many sets with substantial overlap. One way to look at thezig-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. Thezig-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.

This talk will serve as follow-up to the talk given at the TOC Seminar on Tuesday, February 13th.