In light of the nearly immediate failure of the last open question, here is a recap of the progress on the few somewhat more legitimate questions appearing here over the past few years. (Note that most of these questions are not original and appeared other places as well.)
- Derandomiziation of the maximum of a Gaussian process was solved by Raghu Meka in this FOCS’12 paper.
- Conjecture 1 from that post was solved by Jian Ding in the special case of trees and bounded-degree graphs. The conjecture is still open in general.
- Siu On Chan solved the PSD Lifting question in the comments of the post. Since then, the invention of the short code gave a much more sophisticated way of derandomizing Unique Games instances.
- A PTAS for TSP in doubling spaces was solved by Bartal, Gottlieb, and Krauthgamer in this STOC 2012 paper.
- The Dimension reduction in L1 question is still largely open, though Andoni, Naor, and Neiman have reportedly made some progress in an unpublished manucsript (see Remark 5.2 here).
- Capacity scaling in PSD flows was solved, in the non-uniform case, in a STOC 2010 paper with my student Mohammad Moharrami. The case of uniform (all-pairs) flows is still open.
- No progress has been made on improving the quantitative dependence on h in the low-diameter graph partitioning problem.
