Two open problems from this blog were solved recently. First, there is a solution by Bartal, Gottlieb, and Krauthgamer of the Doubling TSP problem. Next, Raghu Meka gave a deterministic procedure to compute the expected supremum of a Gaussian process.

If you’re thirsting for more open problems, I suggest this list on analysis of Boolean functions, compiled by Ryan O’Donnell in conjunction with the 2012 Simons Symposium.

Finally, in the realm of re-proving theorems, let me mention this absolutely gorgeous proof by Lovett and Meka of Spencer’s six standard deviations suffice theorem in discrepancy theory. The proof is constructive (i.e., there exists a polynomial-time algorithm to construct the 2-coloring) as in recent groundbreaking work of Bansal, but unlike Bansal’s proof is independent of Spencer’s bound. It also happens to be elementary and beautiful; my thanks to Aravind Srinivasan for pointing it out.

### Like this:

Like Loading...

*Related*