Direct product testing, parallel repetition and foams

Avi Wigderson
Institute for Advanced Study

Here is a way to test the consistency of two people (or search engines). From a large collection of possible questions, pick at random 2k-m questions, and ask Alice the first k and Bob the last k. Suppose they answer consistently the m common questions with probability p. Can we infer that they have a "consistent world view"?
Here a "world view" is an answer to each possible question, extended to k-subsets. It is no hard to see that there can be at least 1/p completely different world views, so that if each k-subset of questions is consistent with a random one of these, such a consistency test will pass with probability p. We explore parameters under which an inverse theorem (to this and related questions) can be proved. This yields combinatorial "discrete rigidity" phenomena with somewhat peculiar behavior when compared to similar questions in algebraic settings.
This part is based on work with Impagliazzo and Kabanets. We also briefly explain how the motivation for such questions arises from "hardness amplification" of functions, efficient PCP constructions and "parallel repetition" theorems for games. We also show how these investigations lead to surprising geometric constructions of foams (periodic tilings) in high dimensions. The result on foams is joint with Kindler, O'Donnell and Rao.

Back to Workshop IV: Analytical Methods in Combinatorics, Additive Number Theory and Computer Science