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 http://sigact.acm.org/~stoc05/STOC2005.html or http://www.cs.jhu.edu/~stoc05/STOC2005.html.
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
USA
To facilitate notification, authors submitting printed copies should also send an email to stoc05@cs.jhu.edu, 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 stoc05@cs.jhu.edu 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 http://sigact.acm.org/prizes/bestpaper.
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 http://sigact.acm.org/~stoc05/STOC2005.html. The list of past winners can be found at http://sigact.acm.org/prizes/student.
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 stoc05@cs.jhu.edu. 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.