January 11, Tuesday
12:00 – 14:00
Motivated by this question, we study the random composition of a small family of $O(n^3)$ simple permutations on ${0,1}^n$. Specifically we ask how many randomly selected simple permutations need be composed to yield a permutation that is close to k-wise independent. We improve on the results of Gowers 1996 and Hoory, Magen, Myers and Rackoff 2004, and show that up to a polylogarithmic factor,$n^2*k^2$ compositions of random permutations from this family suffice. We also introduce the new notion of closeness to k-wise independence against adaptive adversaries and show the constructed permutation has the stronger property. In addition, our results give an explicit construction of a degree $O(n^3)$ Cayley graph of the alternating group of $2^n$ objects with a spectral gap $\Omega(1/(n^2 * 2^n))$, which is a substantial improvement over previous constructions.
This question is essentially about the rapid mixing of a certain Markov chain, and the proofs are base on the comparison technique.
Joint work with Alex Brodsky.
Short bio:
I graduated the Hebrew University at 2002 with a Ph.D thesis titled "On graphs of high girth", supervised by Prof. Nati Linial. After that I have been a Postdoctoral Fellow at the University of Toronto and recently at the University of British Columbia.
My primary research is on graph eigenvalues, expansion and their connection to other fields. These include error correcting codes, geometric proof systems, cryptography, and computation. Of particular interest to me are the extremal properties of irregular graphs, and graphs of high girth. In addition, I have a rich practical experience from working in the industry in programming, real time systems, OS internals, VLSI design, and digital signal processing.