STOC 2017 accepted papers

The list of accepted papers to STOC 2017 has just been released. Following the trend in recent years there are quite a few learning theory papers! I have already blogged about the kernel-based convex bandit algorithm; as well as the smoothed poly-time local max-cut (a.k.a. asynchronous Hopfield network). Some of the other learning papers that caught my attention: yet again a new viewpoint on acceleration for convex optimization; some progress on the complexity of finding stationary point on non-convex functions; a new twist on tensor decomposition for poly-time learning of latent variable models; an approximation algorithm for low-rank approximation in ell_1 norm; a new framework to learn from adversarial data; some progress on the trace reconstruction problem (amazingly the exact same result was discovered independently by two teams, see here and here); new sampling technique for graphical models; new relevant statistical physics result; faster submodular minimization;  and finally some new results on nearest neighbor search.