Call For Papers
36th ACM Symposium on Theory of Computing (STOC 2004)

Chicago, IL
June 13-15, 2004

Submission deadline: 4:59 pm EST, Wednesday, November 5, 2003

The 36th ACM Symposium on Theory of Computing (STOC 2004), sponsored by the ACM Special Interest Group on Algorithms and Computation Theory, will be held in Chicago, IL, June 13 to 15, 2004. 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. Information on local arrangements will be available from the webpage at

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, 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.

Electronic submission: Authors are strongly encouraged to submit their Extended Abstracts electronically in PDF or postscript format (PDF preferred). We are using the electronic submission system CMT (Conference Management Toolkit) of Microsoft Research. The submission site is CMT appears to be quite user-friendly but before going to the CMT website, please read our submission instructions at

Unprintable submissions and submissions not formatted for 8.5x11 inch paper will be rejected without consideration of their merits. The Extended Abstract (by electronic submission) MUST be received by 4:59 pm EST November 5, 2003 (Wednesday). This is a FIRM deadline; late submissions will not be considered. Authors who cannot submit electronically, please read the instructions for hard copy submission. 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 2004) will not be considered for acceptance at STOC 2004. 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 February 4, 2004.

If you plan to submit the same paper to ICALP'04, click here.

Deadline for Accepted Papers: A camera-ready copy of each accepted paper is required by March 8, 2004. (Note that this deadline is one week earlier than the previously published deadline.)

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 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. This must be certified in an email message sent to the Program Committee Chair. For details, please go to The list of past winners can be found at

Program Chair: Laszlo Babai, Department of Computer Science, University of Chicago, 1100 E 58th St, Chicago, IL 60637-1581, Telephone: 773-702-3486. Email:

Program Committee

Local Arrangement Co-Chairs: Ming-Yang Kao, Department of Computer Science, Northwestern University, Evanston, IL. Email:, and
Janos Simon, Department of Computer Science, University of Chicago, 1100 E 58th St, Chicago, IL 60637-1581, Telephone: 773-702-3488. Email:

The authentic and up-to-date version of this document can be found at

This document was last updated on 09/12/03.

Go to the Submission Instructions

Back to STOC'04 HOME.