Monthly Archives: October 2016
Local max-cut in smoothed polynomial time
Omer Angel, Yuval Peres, Fan Wei, and myself have just posted to the arXiv our paper showing that local max-cut is in smoothed polynomial time. In this post I briefly explain what is the problem, and I give a short … Continue reading
Prospective graduate student? Consider University of Washington!
This post is targeted at prospective graduate students, especially foreigners from outside the US, who are primarily interested in optimization but also have a taste for probability theory (basically readers of this blog!). As a foreigner myself I remember that … Continue reading
Guest post by Miklos Racz: Entropic central limit theorems and a proof of the fundamental limits of dimension estimation
In this post we give a proof of the fundamental limits of dimension estimation in random geometric graphs, based on the recent work of Bubeck and Ganguly. We refer the reader to the previous post for a detailed introduction; here … Continue reading