The FOCS program is now online here.
Congratulations to Yin Tat Lee and Aaron Sidford for winning the best paper and the best student paper awards for their paper “Solving Linear Programs in O˜(√rank) Iterations and Faster Algorithms for Maximum Flow“. They made an important advance in the theory of interior point methods by showing that you can actually converge faster, and match the non-constructive iteration-bound of Nesterov and Nemirovsky, if you modify on the fly the path the algorithm is taking. On top of that (and with a lot of extra work) they showed that these ideas can yield faster algorithms for Max-Flow in a broad range of parameters. It’s always nice to see how trying to solve one problem such as Max-Flow can often yield unexpected payoffs in areas that at first sight may seem unrelated (Max-Cut is another great example of this phenomenon) .
Of course, as I and some others mentioned, there are many other great papers in the conference, and the workshop/tutorial day is looking very good too. The schedule is also perhaps a bit saner this time around, with a bit less parallelism, and somewhat longer breaks than usual, so I am hoping to see many of this blog’s readers in Philadelphia in October! (Deadline for early registration and discounted hotel rate is September 22nd.)
Keeping up with the times, FOCS now has a more mobile-friendly website (thanks to Wolfgang Richter that gave me access to the codebase of the SOSP 2013 website) and even a twitter account ( @focs14 ). We might even have an app – more on that later.
Windows On Theory 