STOC 2002

34th ACM Symposium on Theory of Computing

Montréal, Québec, Canada

May 19-21, 2002



The 34th ACM Symposium on Theory of Computing (STOC2002), sponsored by the ACM Special Interest Group on Algorithms and Computation Theory, will be held in Montreal, Canada, May 19-21, 2002.  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. STOC2002 is sponsored by SIGACT (ACM Special Interest Group on Algorithms and Computation Theory). It is co-located with the 17th Conference on Computational Complexity (Complexity 2002).


Committee Members:

Pankaj Agarwal, Alan Borodin, Sam Buss, Shafi Goldwasser, Rao Kosaraju, Richard Ladner, Gary Miller, Michael Mitzenmacher, Satish Rao, John Reif (chair), Micha Sharir, Paul Spirakis, Mikkel Thorup, and Leslie Valiant.


Program Chair:

John H. Reif, D223 LSRC Building, Department of Computer Science, Research Drive, Duke University, Box 90129, Durham, NC 27708-0129 USA.

Telephone: (919)-660-6568. E-mail: .


Conference Chair:

Pierre McKenzie, Laboratoire d'informatique théorique et quantique, Département d'informatique et de recherche opérationnelle, Université de Montréal, C.P. 6128 succursale Centre-ville, Montréal (Québec) H3C 3J7 Canada.

Telephone (514)-343-6176. E-mail: .


Key Information:


Submission deadline:  5:59 pm EST November 12, 2001.


Notification date: January 20, 2002.


Deadline for Accepted Papers:  February 20, 2002.


STOC 2002 web page:  


Details of Submissions:

The following page describes in detail the abstract submission page restrictions and format, relevant dates and deadlines, restrictions on simultaneous submissions, joint submissions to Computational Complexity 2002, as well as the best student paper award. A detailed description of the electronic submission process is given at

Further Information on STOC2002 Submissions


Simultaneous submissions and the Joint Session:

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 2002) will not be considered for acceptance at STOC 2002. SIGACT policy does not generally allow simultaneous submissions of the same (or essentially the same) abstract material to another conference with a published proceedings. However, this year, there will be a special exception: STOC will be collocated with the Computational Complexity 2002 conference, and co-submissions will be allowed for a Joint Session of these two conferences if the program chairs are notified via email. Abstracts that are accepted for the Joint Session will appear in the STOC'02 proceedings, and a 1-page version of the abstract will appear in the Complexity proceedings.  Abstracts not accepted for the Joint Session will still be eligible for acceptance to the Computational Complexity 2002 conference. More information on the conference, including details of local arrangements, is given on the STOC 2002 web page, 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. 


Abstract submission:

Authors are strongly encouraged to submit their extended abstracts electronically. A detailed description of the electronic submission process is 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 will be made available (with details available at the web site listed above).  The abstract (by electronic submission) MUST be received by 5:59 pm EST November 12, 2001.  This is a FIRM deadline; late submissions will be rejected. Authors who do not wish to 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 5:59 pm EST November 5, 2001; (b) The authors must send 15 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 5:59 pm EST November 12, 2001. (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 November 5, 2001.  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.  



Authors will be sent notification of acceptance or rejection by e-mail on or before January 20,2002. 


Deadline for Accepted Papers: A camera-ready copy of each accepted paper is required by February 20, 2002, which is a firm deadline. 


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 submission cover letter or (for electronic submissions) the registration process.