The Fourth Moment Method

Abstract

Higher moment analysis has typically been used to upper bound certain functions. In this paper, we introduce a new combinatorial method to lower bound the expectation of the absolute value of a random variable X by the expectation of a quartic in X. In the special case where we are looking at the absolute value of a (weighted) sum of {-1,+1} unbiased random variables, we achieve tight bounds, using only a fourth moment, for the total discrepancy of a set system. Because the fourth moment depends only on 4-wise independence, our bounds will hold over polynomially sized distributions, and so these bounds will be directly applicable in removing randomness to obtain NC algorithms. We obtain the first NC algorithms for the problems of total discrepancy, maximum acyclic subgraph, tournament ranking, the Gale--Berlekamp switching game, and edge discrepancy. We show that for most of these applications it is truly necessary to consider a fourth moment by exhibiting a 3-wise independent distribution which does not achieve the required bounds. Our method is strong enough to give a new combinatorial bound on tournament ranking.