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 fraction of constraints are satisfiable, finds an assignment satisfying a constant fraction of constraints in time . This is now officially announced in an earlier (public) paper by Arora, Impagliazzo, Matthews and Steurer, which presented a slower algorithm running in time where .
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 approximation for sparsest cut or 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 , the conjecture is that if is any function such that
then there is a matrix and a vector such that
where the probability in the conclusion is independent of and is polynomial in . Various proofs were known achieving a bound of . The first proof, due to Samorodnitsky achieves, I believe, a bound of , while the results from this paper should imply a bound of where we use the notation .
At the conference, Ben Green announced a result of Schoen implying a subexponential bound of .
The proof begins with the standard step of applying a theorem of Ruzsa to find a subset such that , and on is a “Freiman 16-homomorphism,” meaning that for every 32 elements of such that
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 of all the elements that can written as with , and we define a function on by setting
which is a well-posed definition because is a Freiman 16-homomorphism. (It would have been sufficient if had been an 8-homomorphism.) Note that for every such that we have
Now the result of Schoen implies that if is a subset of of size , then there is a subspace of dimension such that is entirely contained in .
Previously, it was known how to get a subspace of dimension , by adapting a technique of Chang (see this survey paper).
Note that is now a linear map on , and that it agrees with on . (I cannot reconstruct how this last step follows, however — maybe that claim is that agrees with on a fraction of elements of ? ) It now just remains to extend, arbitrarily, to a linear map over the entire space.