STOC 50 Part I

This week I'm in Los Angeles attending the 50th Symposium on the Theory of Computing. Most attendees weren't even born before the first STOC. Many of them weren't even born when I went to my first STOC in 1986 in Berkeley.

Most of the festivities come later but let me mention the best paper winners, both of whose titles give the theorem. A Constant-Factor Approximation Algorithm for the Asymmetric Traveling Salesman Problem by Ola Svensson, Jakub Tarnawski and László Végh won the best paper and An almost-linear time algorithm for uniform random spanning tree generation by Aaron Schild won the Danny Lewin Best Student Paper Award. For those who don't know, Danny Lewin was an MIT grad student and co-founder of Akamai who lost his life on 9/11.

A nice feature of the STOC theory fest, a tradition started last year, are the many invited talks. This morning we saw Stanford statistician Emmanuel Candes talk about irreproducible scientific results. The scientific method typically makes hypotheses, designs experiments to test predictions, updates the hypotheses and repeat. Today with we automatically generate hypotheses from big data using machine learning techniques which often leads to false positive correlations. Candes talked about his approach to mitigating this problem with knockoff variables.

I also enjoy the senior junior lunch which I had today with students Rachit Nimavat, Jiyu Zhang and Zhixian Lei. Great discussions about the theory life.