HD-Combinatorics: Amnon Ta-Shma, "Bias samplers and reducing overlap in random walks over graphs"

Abstract: 

The expander Chernoff bound states that random walks over expanders are good samplers, at least for a certain range of parameters. In this talk we will be interested in “Parity Samplers” that have the property that for any test set, about half of the sample sets see the test set an *even* number of times, and we will check whether random walks over expanders are good parity samplers. We will see that:

1. Random walks over expanders fare quite well with the challenge, but,
2. A sparse Random complex does much better.

We will then discuss how to get close to optimal with a variant of the zig-zag product.

Time permitting I will also discuss overlap in high dimensional complexes. Recent HD constructions get (somewhat weak) samplers but with amazing, highly non-trivial overlap. In this sense, the work I present goes in the other direction. For us, overlap is bad because it hurts the next to optimal sampling property of a sparse random set (which is w.h.p an excellent sampler, and almost completely avoids any meaningful overlap). The zig-zag product is a way to reduce the overlap of random walks over expanders while keeping sampling relatively good. Thus, in a sense we try to reduce overlap while HD expander constructions try to construct meaningful overlap, even if it is expansive, and it hurts sampling properties.

Date: 

Mon, 08/01/2018 - 14:00 to 16:00