Call For Papers
35th ACM Symposium on Theory of Computing (STOC 2003)

San Diego, CA
June 9-11, 2003

The 35th ACM Symposium on Theory of Computing (STOC 2003), sponsored by the ACM Special Interest Group on Algorithms and Computation Theory, will be held in San Diego, CA, June 9 to 11, 2003. 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. This year, STOC 2003 will be part of the Federated Computing Research Conference (FCRC 2003, June 7-14, 2003); information about the other conferences which are part of FCRC 2003 can be obtained from More information about STOC 2003, including details of local arrangements, will be available from the conference webpage at

Abstract format: Authors should submit an extended abstract (not a full paper). An abstract should start with the title of the paper, each author's name, affiliation, and e-mail address, followed by a one-paragraph 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 on letter-size paper, using reasonable 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. Abstracts deviating significantly from these guidelines risk rejection without consideration of their merits.

Submission deadline: 11:59 pm EST November 6, 2002.

Abstract submission: Authors are strongly encouraged to submit their extended abstracts electronically. A detailed description of the electronic submission process can be found at Unprintable Postscript and Postscript submissions not formatted for 8.5x11 inch paper will be rejected without consideration of their merits. For those unsure of the printability of their Postscript, a test printing service is available (with details available at the web site listed above). The abstract (by electronic submission) MUST be received by 11:59 pm EST November 6, 2002. This is a FIRM deadline; late submissions will be rejected. Authors who cannot submit electronically are invited to submit hard copies by the following procedure: (a) The authors must first send an e-mail to the STOC program chair to state the intention of submitting hard copies, by 11:59 pm EST October 30, 2002; (b) The authors must send 16 copies (printed double-sided if possible) of an extended abstract and a cover letter to the STOC program chair (address below) to be received before 11:59 pm EST November 6, 2002. (c) Authors from locations where access to reproduction facilities is severely limited may ask for permission of submitting a single copy by first sending an e-mail to the chair at or before October 30, 2002. 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 2003) will not be considered for acceptance at STOC 2003. 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 e-mail on or before January 28,2003.

Deadline for Accepted Papers: A camera-ready copy of each accepted paper is required by March 12, 2003, which is a FIRM deadline.

Best Paper Award: Starting this STOC 2003, the program committee may designate up to three papers accepted to the conference as STOC Best Papers. Rules for the award(s) 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 indicated in the registration process or in the submission cover letter (for hardcopies). Past winners can be found at

Program Committee Members:

Program Chair: Michel X. Goemans, Room 2-351, Massachusetts Institute of Technology, Cambridge, MA 02139, USA. Telephone: 617-253-2688. E-mail:

Conference Chair: Lawrence L. Larmore, Department of Computer Science, University of Nevada Las Vegas, Las Vegas, NV 89154-4019. E-mail: