Gaussian bounds for noise correlation of functions, submitted

We derive tight bounds on the expected value of products of low influence functions defined on correlated probability spaces. The proofs are based on extending Fourier theory to an arbitrary number of correlated probability spaces, on a generalization of an invariance principle recently obtained with O’Donnell and Oleszkiewicz for multilinear polynomials with low influences and bounded degree and on properties of multi-dimensional Gaussian distributions. Let (Xji: 1 ≤ i ≤ k, 1 ≤ j ≤ n) be a matrix of random variables whose columns X1,..., Xn are independent and identically distributed and such that any two rows Xi, Xj for 1 ≤ i = j ≤ k are independent. Assume further that the values that row Xi takes with non-zero probability are the same no matter how one conditions on the remaining rows X1,..., Xi−1, Xi+1,..., Xk. Our results show that given k functions f1,..., fk taking values in [0, 1] it holds that |E[∏ki=1 fi(Xi)] −∏ki=1 E[fi(Xi)] | < if all influences of the functions fi are smaller than τ(, k) which is independent of n. In words: low influence functions of pairwise independent rows behave like independent random variables. The general statement of our result applies when the rows are not pairwise independent and when (some) of the variables do not have low influences for (some) functions. The results obtained here allow analyzing hyper-graph long-code tests. A number of applications in hardness of approximation assuming the Unique Games Conjecture were obtained using the results derived here in subsequent work by Raghavendra and jointly by Austrin and the author. Our results imply new results on voting schemes in social choice and in additive number theory. In particular we show that among all low influence functions, Majority is asymptotically the most predictable and is (almost) optimal in the context of Condorcet voting