FOCS 2024

Junior/Senior lunch in 80°F Chicago Last summer I attended the Complexity Conference in Ann Arbor for the first time in eight years largely because it was within driving distance. So with FOCS in Chicago this year I didn't have much of an excuse to skip it. I haven't attended a FOCS in person since the 2010 conference in Vegas, though I have been at a few STOCs in that span. 

The 65th IEEE Symposium on Foundations of Computer Science is being held this week at the voco hotel, a beautiful venue in Wolf's Point where the three branches of the Chicago river meet—though you'd never know it from the windowless conference venue on the 14th floor. I'm enjoying reconnecting with colleagues old and new. Sometimes you can go back home again.

Even with triple sessions, we had 12 minute talks for most papers with longer online versions linked from the schedule page. I liked the 12-minute format; with 20 minutes, speakers tend to rush through proofs, while here, they could take their time giving high-level overviews of their papers.

Stats: 274 registrants. 157 students. 16 international. Large compared to recent years but it's not a huge conference. 133 accepted papers chosen among 463 submissions from a program committee of 47 members.

The Knuth Prize winner Rajeev Alur gave his lecture on Specification-guided Reinforcement Learning. 

The Machtey Prize for best student papers goes to Brice Huang for Capacity Threshold for the Ising Perceptron and Meghal Gupta, Mihir Singhal and Hongxun Wu for Optimal Quantile Estimation: Beyond the Comparison Model.

Best paper awards goes to Bernhard Haeupler, Richard Hladík, Václav Rozhoň, Robert Tarjan and Jakub Tětek for Universal Optimality of Dijkstra via Beyond-Worst-Case Heaps (Quanta Article) and Mohsen Ghaffari and Christoph Grunau for Near-Optimal Deterministic Network Decomposition and Ruling Set, and Improved MIS.

Test of time Awards

• FOCS 1994: Given the three papers, Shor's quantum factoring and the Simon paper that inspired him, which I posted about recently, and Expander Codes by Mike Sipser and Dan Spielman. Dan's 1994 talk was a personal favorite, largely because he used pictures without words to effectively convey how to derive error-correcting codes from expander graphs.
• FOCS 2004: Optimal inapproximability results for Max-Cut and other 2-Variable CSPs by Subhash Khot, Guy Kindler, Elchanan Mossel, and Ryan O'Donnell (one of my favorite theorems) and Worst-case to average-case reductions based on Gaussian measures by Daniele Micciancio and Oded Regev. 
• FOCS 2014: Popular conjectures imply strong lower bounds for dynamic problems by Amir Abboud and Virginia Vassilevska Williams

In 2025 FOCS goes down under to Sydney, Australia, December 15-17.