STOC

The papers in this volume were presented at the 44th Annual ACM Symposium on Theory of Computing (STOC 2012), held in New York, NY, May 20-22, 2012. The Symposium was sponsored by the ACM Special Interest Group on Algorithms and Computation Theory (SIGACT).

The program committee met on January 27-28, 2012 in Toronto, Ontario, Canada, and selected 90 papers from 303 detailed abstracts submitted. One pair of papers was merged into a single talk, and one paper was withdrawn, resulting in a total of 88 talks presented at the conference, and 89 papers in this proceedings. The submissions were not formally refereed, and many of them represent reports of continuing research. It is expected that most of them will appear in a more polished and complete form in scientific journals.

In addition to the regular program, there were several other avenues for research presentations. The program committee invited Michael Kearns to present a tutorial in the morning of May 19, 2012, before the main conference, on the topic of Algorithmic Trading and Computational Finance. In the afternoon of May 19, 2012, STOC hosted four workshops, in the areas of: Computational Sustainability, Algorithms for Distributed and Streaming Data, Algorithms for Memory-Sensitive Computing, and the Unique Games Conjecture and Related Advances. Lastly, many additional papers were presented during a poster session held on the evening of May 20, 2012.

From the many outstanding candidates, the STOC program committee selected the following two papers as recipients of the Best Paper Award: "Linear vs. Semidefinite Extended Formulations: Exponential Separation and Strong Lower Bounds" by Samuel Fiorini, Serge Massar, Sebastian Pokutta, Hans Raj and Ronald de Wolf, and "The Cell Probe Complexity of Dynamic Range Counting," by Kasper Green Larsen. The latter of these two papers is also the recipient of the Danny Lewin Best Student Paper Award.