Abstract
In this talk, we establish a dimension-free ell_2 maximal inequality for spherical means on the Hypercube graph {0,1}^n. We explain possible connections to the notorious Unique Games Conjecture.
Combinatorially, this inequality implies the following stronger alternative to the union-bound technique: Assume that we have a binary function f (values 0,1) on the n-dimensional hypercube Hn, with N=2^n vertices. Think of the set X={xin Hn : f(x)=1} as the set vertices that a malicious adversary "spoils". Assume |X|adversary can only spoil up to epsilon fraction of the vertices. Fix a threshold lambda>epsilon. Say a (hamming) sphere S(x,r) or radius r around a point x is "bad" if the adversary has spoiled more than lambda fraction of the points in the shpere. We call a point x "ruined" if there exists a radius r for which the sphere S(x,r) around x is bad. Our maximal inequality implies that for every lambda, there is an absolute constant epsilon (which does not depend on the dimension n) that if the adversary spoils at most epsilon fraction of the points then the "ruined" set is a strict subset of the hypercube. Note that applying a union-bound over radii instead, we would not get any useful inequality for the size of the ruined set.