Let G be a finite Abelian group and A a subset of G. The spectrum of A is the set of its large Fourier coefficients. Known combinatorial results on the structure of spectrum, such as Chang's theorem, become trivial in the regime |A|=|G|α whenever α≤c, where c≥1/2 is some absolute constant. On the other hand, there are statistical results, which apply only to a noticeable fraction of the elements, which give nontrivial bounds even to much smaller sets. One such theorem (due to Bourgain) goes as follows. For a noticeable fraction of pairs γ1,γ2 in the spectrum, γ1+γ2 belongs to the spectrum of the same set with a smaller threshold. Here we show that this result can be made combinatorial by restricting to a large subset. That is, we show that for any set A there exists a large subset A′, such that the sumset of the spectrum of A′ has bounded size. Our results apply to sets of size |A|=|G|α for any constant α>0, and even in some sub-constant regime.

Let f : {0, 1}n → {0, 1} be a boolean function. Its associated XOR function is the two-party function f(x, y) = f(x y). We show that, up to polynomial factors, the deterministic communication complexity of f is equal to the parity decision tree complexity of f. This relies on a novel technique of entropy reduction for protocols, combined with existing techniques in Fourier analysis and additive combinatorics.

The arithmetic regularity lemma due to Green [GAFA 2005] is an analogue of the famous Szemerédi regularity lemma in graph theory. It shows that for any abelian group G and any bounded function f : G → [0, 1], there exists a subgroup H ≤ G of bounded index such that, when restricted to most cosets of H, the function f is pseudorandom in the sense that all its nontrivial Fourier coefficients are small. Quantitatively, if one wishes to obtain that for 1 - ϵ fraction of the cosets, the nontrivial Fourier coefficients are bounded by ϵ, then Green shows that |G/H| is bounded by a tower of twos of height 1/ϵ3. He also gives an example showing that a tower of height Ω(log 1/ϵ) is necessary. Here, we give an improved example, showing that a tower of height Ω(1/ϵ) is necessary.