Computer Science/Discrete Mathematics Seminar II

We give a probabilistic protocol that allows any two points in R^d to agree on a nearby integer lattice point in Z^d . The protocol uses shared randomness, but no communication. If the distance between the two points is delta, the probability of disagreement is as small as O(\delta\sqrt(d)) . This bound is optimal (up to constants) in both parameters. This protocol and its analysis generalizes a recent breakthrough protocol of Raz, which disproved the "strong parallel repetition conjecture", from the discrete to the continuous domain. By repeatedly sampling from this distribution, we obtain a (random) periodic tiling of space, sometimes called "periodic foam". Each "bubble" in this foam naturally has volume 1. The upper bound on the disagreement probability above translates (via the Buffon's needle principle) to show that the expected surface area of this bubble is O(\sqrt(d)). This greatly improves the best previous upper bound was theta(d), not much smaller than the area of a cube – the most trivial periodic tiling of R^d . On the other hand, our upper bound is tight, since the minimal area body of unit volume is the sphere, whose area is \Omega(\sqrt(d)) . This construction reverses a connection, proposed in [FeigeKindlerODonnell 07], between periodic foams and an instance of the parallel repetition problem. Our result resolves a natural geometric optimization problem, that originally arose from Chemistry and Mechanical Engineering motivations (which, to be frank, are mainly in 3 dimensions). We proceed to extend our technique and result to other lattices in R^d, a problem pursued by geometers and physicists. Let V be a matrix of determinant 1, and L = {V x : x 2 Zd} be the lattice generated by V . An extension of our random process above yields bubbles of unit volume which tile R^d with period L, and whose surface area is O(C_L\sqrt(d)) . The constant CL is the expected length of a random unit vector under the transformation V^(-1) ; noting that many matrices V give rise to the same lattice L , the above should be minimized over all such V . While finding the optimal V is a difficult computational problem, we prove a complementary lower bound on C_L , and show that for some lattices is again tight. Joint work with Ryan O'Donnell, Guy Kindler and Avi Wigderson.