Special Section on the Fifty-First Annual IEEE Symposium on Foundations of Computer Science (FOCS 2010)
Lap Chi Lau, Tal Malkin, Ryan O'Donnell, Luca Trevisan · SIAM Journal on Computing · 2014
This special section contains five selected papers from the 50th Annual Symposium on Foundations of Computer Science (FOCS 2010) sponsored by the IEEE Technical Committee on Mathematical Foundations of Computing. The conference was held in Las Vegas, Nevada, October 23-26, 2010. The conference program consisted of 81 papers, which the program committee selected from 270 submissions. The program committee was composed of Scott Aaronson, Dorit Aharonov, Eli Ben-Sasson, Julia Chuzhoy, Ryan O'Donnell, Roberto Grossi, Nick Harvey, Adam Kalai, Nicole Immorlica, Yuval Ishai, Lap Chi Lau, James Lee, Tal Malkin, Joe Mitchell, Dana Moshkovitz, S. Muthukrishnan, Christos Papadimitriou, Sofya Raskhodnikova, Steve Skiena, Mikkel Thorup, Luca Trevisan, and Eric Vigoda. Each of the five papers appearing in this issue was subject to the standard refereeing process of the SIAM Journal on Computing. In “The Monotone Complexity of $k$-Clique on Random Graphs," Ben Rossman proves that monotone circuits that solve the $k$-clique problem in random graphs must have size $\omega(n^{k/4})$, establishing the first average-case monotone lower bound. Andreas Björklund, in the paper “Determinant Sums for Undirected Hamiltonicity," develops the first improvement to the $\tilde O(2^n)$ dynamic programming algorithm for Hamiltonian circuit: Björklund's algorithm runs in time $\tilde O(1.657^n)$. The paper “Distance Oracles Beyond the Thorup--Zwick Bound" by Mihai Pătraşcu and Liam Roditty presents the first improvement in ten years for the problem of compactly representing an approximation to all-pairs shortest path distances in a graph. Shaddin Dughmi and Tim Roughgarden show how to convert any approximation algorithm for a certain class of problems into a truthful mechanism in the paper “Black-Box Randomized Reductions in Algorithmic Mechanism Design." Ioannis Koutis, Gary Miller, and Richard Peng, in the paper “Approaching Optimality for Solving SDD Linear Systems," present a new nearly linear time algorithm for the problem of solving systems of linear equations that are symmetric and diagonally dominant. We wish to thank Madhu Sudan and Leonard Schulman, the former and current Editors-in-Chief of SICOMP, for being very generous with their time as they helped us in this project. We also wish to thank Heather Blythe of SIAM and the anonymous referees.