STOC

The papers in this volume were presented at the Fourtieth Annual ACM Symposium on Theory of Computing (STOC 2008), held in Victoria, British Columbia, May 17--20, 2008. The Symposium was sponsored by the ACM Special Interest Group on Algorithms and Computation Theory (SIGACT). This volume also contains abstracts for invited talks by Jennifer Rexford and David Haussler, as well as a tutorial on the analysis of Boolean functions, delivered by Ryan O'Donnell.

The submitted papers in many cases 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 response to the Call for Papers, a record 325 submissions were received by the November 19, 2007 5:00 PM PST deadline (a short grace period was extended), of which 5 were eventually withdrawn. Although the submissions were not formally refereed, each received careful consideration. The committee held lengthy on-line discussions, followed by a physical meeting January 18-20, in Mountain View, California, attended by 20 of the 21 program committee members. Eventually, 80 papers were selected for inclusion in the program. Of these, the committee chose two recipients for the Best Paper Award: "Algorithms and Inapproximability Results For Every CSP?" by Prasad Raghavendra, and "Optimal Hierarchical Decompositions for Congestion Minimization in Networks" by Harald Räcke. The committee also awarded the Danny Lewin Best Student Paper award to the former.

A few months before the submission deadline, the committee began a discussion of the role of conceptual and outreach papers, concluding that these should be thoroughly integrated into the conference. There are many merits a paper can have, including mathematical sophistication, conceptual clarity, and extending the reach of theory. The committee reaffirmed the importance of all of these, while recognizing that none is a sine qua non of an excellent theory paper. To this end, the call for papers was modified to encourage outreach papers, and a conscientious effort was made throughout the reviewing process to recognize outreach, conceptual innovation, and simplicity as strengths.