Special Section on the Forty-First Annual ACM Symposium on Theory of Computing (STOC 2009)
Nicole Immorlica, Jonathan Katz, Michael Mitzenmacher, Rocco A. Servedio, Chris Umans · SIAM Journal on Computing · 2012
This issue of SICOMP contains nine specially selected papers from the Forty-first Annual ACM Symposium on the Theory of Computing, otherwise known as STOC 2009, held May 31 to June 2 in Bethesda, Maryland. The papers here were chosen to represent both the excellence and the broad range of the STOC program. The papers have been revised and extended by the authors, and subjected to the standard thorough reviewing process of SICOMP. The program committee consisted of Susanne Albers, Andris Ambainis, Nikhil Bansal, Paul Beame, Andrej Bogdanov, Ran Canetti, David Eppstein, Dmitry Gavinsky, Shafi Goldwasser, Nicole Immorlica, Anna Karlin, Jonathan Katz, Jonathan Kelner, Subhash Khot, Ravi Kumar, Leslie Ann Goldberg, Michael Mitzenmacher (Chair), Kamesh Munagala, Rasmus Pagh, Anup Rao, Rocco Servedio, Mikkel Thorup, Chris Umans, and Lisa Zhang. They accepted 77 papers out of 321 submissions. We briefly describe the papers that appear here. In “Bit-Probe Lower Bounds for Succinct Data Structures” Emanuele Viola considers lower bounds for representing lists of values where one also wants to be able to probe the structure that maintains the values in order to for example determine the $i$th value in the list efficiently. In “Homology Flows, Cohomology Cuts” Jeff Erickson, Erin Chambers, and Amir Nayyeri provide an algorithm to compute maximum flows in surface-embedded graphs in near-linear time. In “Approximating Edit Distance in Near-Linear Time” Alexandr Andoni and Krzysztof Onak give the first sub-polynomial approximation of the edit distance that runs in near-linear time. In “Online and Stochastic Survivable Network Design” Anupam Gupta, Ravishankar Krishnaswamy, and R. Ravi examine approximation algorithms for finding a subgraph of minimum cost that maintain given connectivity constraints, in a number of online and stochastic settings. In “Universally Utility-Maximizing Privacy Mechanisms” Arpita Ghosh, Tim Roughgarden, and Mukund Sundararajan study differential privacy mechanisms, giving an approach that is simultaneously expected loss-minimizing in terms of utility for all users subject to a differential privacy constraint. In “3-Query Locally Decodable Codes of Subexponential Length” Klim Efremenko provides the first unconditional construction for 3-query locally decodable codes with subexponential codeword length. In “Twice-Ramanujan Sparsifiers” Joshua Batson, Daniel Spielman, and Nikhil Srivastava provide a deterministic, polynomial time algorithm for determining a spectral sparsifier of a graph---that is, a graph with a linear number of edges that approximates the graph in terms of its Laplacian matrix. In “New Direct-Product Testers and 2-Query PCPs” Russell Impagliazzo, Valentine Kabanets, and Avi Wigderson present several new results for probabilistically checkable proofs (PCPs), including new 3-query tests and 2-query tests leading to novel 2-query PCPs. In “Max Cut and the Smallest Eigenvalue” Luca Trevisan develops an elegant new approximation algorithm for Max Cut based on spectral partitioning methods, where the approximation ratio is 0.531 generally, but it also performs particularly well when the optimal solution cuts a large fraction of the edges. We thank the authors and the program committee for their hard work, and especially thank the reviewers for their work in evaluating and improving the submitted papers.