  Let eta_i be iid Bernoulli random variables, taking values -1,1 with
probability 1/2. Given a multiset V of n integers v_1,..., v_n, we define the
concentration probability as rho(V) := sup_{x} Pr(v_1 eta_1+...+ v_n eta_n=x).
A classical result of Littlewood-Offord and Erdos from the 1940s asserts that
if the v_i are non-zero, then rho(V) is O(n^{-1/2}). Since then, many
researchers obtained improved bounds by assuming various extra restrictions on
V. About 5 years ago, motivated by problems concerning random matrices, Tao and
Vu introduced the Inverse Littlewood-Offord problem. In the inverse problem,
one would like to give a characterization of the set V, given that rho(V) is
relatively large. In this paper, we introduce a new method to attack the
inverse problem. As an application, we strengthen a previous result of Tao and
Vu, obtaining an optimal characterization for V. This immediately implies
several classical theorems, such as those of Sarkozy-Szemeredi and Halasz. The
method also applies in the continuous setting and leads to a simple proof for
the beta-net theorem of Tao and Vu, which plays a key role in their recent
studies of random matrices. All results extend to the general case when V is a
subset of an abelian torsion-free group and eta_i are independent variables
satisfying some weak conditions.
