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.

About these ads