Solved problems, open problems, and re-solved problems

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.

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s