STOC

The papers in this volume were presented at the Thirty-Fifth Annual ACM Symposium on Theory of Computing (STOC 2003), held in San Diego, California, June 9-11, 2003. The Symposium is sponsored by the ACM Special Interest Group on Algorithms and Computation Theory (SIGACT).In response to a call for papers, 270 paper submissions were received. All were submitted electronically. The program committee conducted its deliberations partly in a physical meeting in Baltimore, MD, on January 12 to 14, 2003 and partly electronically in the ten days before and after the physical meeting. The program committee selected 80 papers from among the submissions. The papers encompass a wide variety of areas of theoretical computer science. The submissions were not refereed in a detailed fashion as for journal submissions, and many of these papers represented reports of continuing research. It is expected that most of them will appear in a more complete form in scientific journal.The program committee has selected two papers for the STOC Best Paper Award. These are "Derandomizing Polynomial Identity Tests Means Proving Circuit Lower Bounds" by Valentine Kabanets and Russell Impagliazzo and "New Lattice Based Cryptographic Constructions" By Oded Regev. Starting this year, the STOC Best Student Paper Award has been renamed the Danny Lewin Best Student Paper Award in honor of the late Daniel Lewin. The program committee has awarded the Danny Lewin Best Student Paper Award to Thomas P. Hayes for his paper "Randomly Coloring Graphs of Girth At Least Five." During the conference, Miklós Ajtai was awarded the Donald E.Knuth Prize and gave a plenary talk.