I was at a conference last week, at which I heard two pieces of mathematical gossip.

One was that Arora, Barak and Steurer have developed an algorithm that, given a Unique Games in which a $1-\epsilon$ fraction of constraints are satisfiable, finds an assignment satisfying a constant fraction of constraints in time $2^{n^{poly(\epsilon)}}$. This is now officially announced in an earlier (public) paper by Arora, Impagliazzo, Matthews and Steurer, which presented a slower algorithm running in time $2^{\alpha n}$ where $\alpha = exp(-1/\epsilon)$.

I suppose that the next targets are now the approximation problems for which the only known hardness is via unique games. Is there a subexponential algorithm achieving $\log\log n$ approximation for sparsest cut or $1.99$ approximation for Vertex Cover?

The other news is on the Polynomial Ruzsa-Freiman conjecture, one of the main open problems in additive combinatorics. Apologies in advance to readers if I get some details wrong. In the special case of $\mathbb{F}_2$, the conjecture is that if $F: \mathbb{F}_2^n \rightarrow \mathbb{F}_2^m$ is any function such that

$\mathbb{P}_{x,y,z} [ F(x) + F(y) + F(z)= F(x+y+z) ] \geq \epsilon$

then there is a matrix $M$ and a vector $b$ such that

$\mathbb{P}_{x} [ F(x) = Mx + b ] \geq \epsilon^{O(1)}$

where the probability in the conclusion is independent of $n,m$ and is polynomial in $\epsilon$. Various proofs were known achieving a bound of $exp(-poly(1/\epsilon)$. The first proof, due to Samorodnitsky achieves, I believe, a bound of $exp(-O(1/\epsilon^2))$, while the results from this paper should imply a bound of $exp(-\tilde O(1/\epsilon))$ where we use the notation $\tilde O(n) := O(n \log n)$.

At the conference, Ben Green announced a result of Schoen implying a subexponential bound of $1/2^{2^{\sqrt{\log 1/\epsilon}}}$.

The proof begins with the standard step of applying a theorem of Ruzsa to find a subset $A\subseteq \mathbb{F}_2^n$ such that $|A| \geq \epsilon^{O(1)} 2^n$, and $F$ on $A$ is a “Freiman 16-homomorphism,” meaning that for every 32 elements of $A$ such that

$a_1 + \cdots + a_{16} = a_{17} + \cdots + a_{32}$

we have

$F(a_1) + \cdots + F(a_{16}) = F(a_{17}) + \cdots + F(a_{32})$

The choice of 16 is just whatever makes the rest of the proof work. The theorem of Ruzsa works for any arbitrarily large constant. Then we consider the set $B := 8A$ of all the elements that can written as $a_1 + \cdots + a_8$ with $a_i \in A$, and we define a function $F'$ on $8A$ by setting

$F'(a_1 + \cdots + a_8) := F(a_1) + \cdots + F(a_8)$

which is a well-posed definition because $F$ is a Freiman 16-homomorphism. (It would have been sufficient if $F$ had been an 8-homomorphism.) Note that for every $b_1,b_2,b_3,b_4 \in B$ such that $b_1 + b_2 = b_3 + b_4$ we have

$F'(b_1) + F'(b_2) = F'(b_3) + F'(b_4)$

Now the result of Schoen implies that if $A$ is a subset of $\mathbb {F}_2^n$ of size $2^n/K$, then there is a subspace $V$ of dimension $n - 2^{O(\sqrt {\log K})}$ such that $V$ is entirely contained in $8A$.

Previously, it was known how to get a subspace of dimension $n - \tilde O(K)$, by adapting a technique of Chang (see this survey paper).

Note that $F'$ is now a linear map on $V$, and that it agrees with $F$ on $V$. (I cannot reconstruct how this last step follows, however — maybe that claim is that $F$ agrees with $F'$ on a $poly(\epsilon)$ fraction of elements of $V$? ) It now just remains to extend, arbitrarily, $F'$ to a linear map over the entire space.