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.
Copyright. All Rights Reserved.