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.