STOC 2005 Call For Papers

Baltimore, MD - May 22-24, 2005

Submission deadline: 5:59 pm EST, Thursday, November 4, 2004

The 37th ACM Symposium on Theory of Computing (STOC 2005), sponsored by the ACM Special Interest Group on Algorithms and Computation Theory, will be held in Baltimore, MD, May 22 to 24, 2005. Papers presenting original research on theoretical aspects of computer science are sought. Typical, but not exclusive, topics of interest include algorithms and data structures, complexity theory, cryptography, computational algebra and geometry, algorithmic graph theory, applications of logic, machine learning, parallel and distributed computing, theoretical aspects of databases, information retrieval, and networks, computational biology, quantum computation and other alternative models of computation.

Submission format: Authors should submit an extended abstract (not a full paper). The extended abstract should start with the title of the paper, each author's name, affiliation, and email address, followed by a brief (one or two paragraphs) summary of the results to be presented. This should then be followed by a technical exposition of the main ideas and techniques used to achieve these results, including motivation and a clear comparison with related work. The abstract should not exceed 10 single-spaced pages (excluding bibliography) on letter-size (8 1/2 x 11 inch) paper and should be in single-column format, using at least 1 inch margins and at least 11-point font. If the authors believe that more details are essential to substantiate the main claims of the paper, they may include a clearly marked appendix that will be read at the discretion of the program committee. Submissions deviating significantly from these guidelines risk rejection without consideration of their merits.

Abstract Submission: Authors are strongly encouraged to submit their extended abstracts electronically. A detailed description of the electronic submission process is available at or

Authors who cannot submit electronically must send 21 printed copies (double-sided preferred) of an extended abstract, together with a cover letter, to:

Ronald Fagin
STOC 2005 Program Chair
IBM Almaden Research Center, Dept. K53/B2
650 Harry Road
San Jose, CA 95120

To facilitate notification, authors submitting printed copies should also send an email to, indicating that they are submitting in this manner. Put "Hardcopy Submission" in the subject line. The abstract MUST be received by 5:59 pm EST November 4, 2004 or postmarked by October 25, 2004. Late submissions will be rejected. Authors from locations where access to reproduction facilities is severely limited may ask for permission of submitting a single copy by first sending an email to at or before October 21, 2004.

Submissions will be judged solely on the basis of the extended abstract submitted by the deadline - post-deadline revisions will NOT be taken into consideration.

Simultaneous Submissions: According to SIGACT policy, abstract material which has been previously published in another conference proceedings or journal (or which is scheduled for publication prior to July 2005) will not be considered for acceptance at STOC 2005. SIGACT policy does not allow simultaneous submissions of the same (or essentially the same) abstract material to another conference with a published proceedings.

Notification: Authors will be sent notification of acceptance or rejection by email on or before January 28, 2005.

Deadline for Accepted Papers: A camera-ready copy of each accepted paper is required by March 1, 2005.

Presentation of Accepted Papers: One author of each accepted paper will be expected to present it at the conference.

Best Paper Award: The program committee may designate up to three papers accepted to the conference as STOC Best Papers. This is a new award, started at STOC 2003. Every submission is automatically eligible for this award. Rules for the award can be found at

Danny Lewin Best Student Paper Award: A prize of $500 will be given to the author(s) of the best student- authored paper (or split between more than one paper if there is a tie). A paper is eligible if all of its authors are full-time students at the time of submission. To inform the program committee about its eligibility, simply add "eligible for best student paper" to "notes:" when registering the paper. For details, please go to The list of past winners can be found at

Program Chair: Ronald Fagin, IBM Almaden Research Center

Program Committee:

Gerth St°lting Brodal University of Aarhus
Harry Buhrman CWI and University of Amsterdam
Jin-Yi Cai University of Wisconsin, Madison
Cynthia Dwork Microsoft Research, Silicon Valley
Ronald Fagin (chair) IBM Almaden Research Center
Martin Farach-Colton Rutgers University
Anupam Gupta Carnegie Mellon University
Sariel Har-Peled University of Illinois, Urbana-Champaign
Russell Impagliazzo University of California, San Diego
Kamal Jain Microsoft Research, Redmond
Adam Kalai Toyota Technological Institute
David Karger Massachusetts Institute of Technology
Claire Kenyon ╔cole Polytechnique
Subhash Khot Georgia Institute of Technology
Ravi Kumar IBM Almaden Research Center
Moni Naor Weizmann Institute of Science
Ryan O'Donnell Institute for Advanced Study
Toniann Pitassi University of Toronto
Tim Roughgarden Stanford University
Alistair Sinclair University of California, Berkeley
Amnon Ta-Shma Tel Aviv University

Tutorials Chair: Cynthia Dwork, Microsoft Research

Local Arrangements Chair: Christian Scheideler, Johns Hopkins University

Questions and Comments: Please direct all of your questions and comments to If you want the email to be forwarded to a particular person of the STOC 2005 committee, please mention that person in the subject line.