Call For Papers 2000 ACM Symposium on Theory of Computing Portland, Oregon May 21-23, 2000 The 32nd ACM Symposium on Theory of Computing (STOC), sponsored by the ACM Special Interest Group on Algorithms and Computation Theory, will be held in Portland, Oregon, May 21-23, 2000. Papers presenting original research on theoretical aspects of computer science are sought. Typical, but not exclusive, topics of interest include algorithmic graph theory, algorithms and data structures, applications of logic, biological computing, computational biology, complexity theory, cryptography, computational algebra, computational geometry, machine learning, parallel and distributed computation, and probabilistic computation. More information on the conference, including details of local arrangements, will be available on the STOC 2000 web page, at http://sigact.acm.org/stoc00/. 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 encouraged to submit their extended abstracts electronically. A detailed description of the electronic submission process will be available at http://sigact.acm.org/~stoc00/STOC00.html. Unprintable Postscript and Postscript submissions not formatted for 8.5x11 inch paper risk rejection 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 October 12, 1999. 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 October 6, 1999; (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 October 11, 1999 or postmarked by October 6 and sent via express mail. (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 before 5:59 pm EST October 6, 1999. 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 May 2000) will not be considered for acceptance at STOC 2000. In addition, 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 6, 2000. A camera-ready copy of each accepted paper is required by February 18, 2000, 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. Committee Members: Charles Bennett, Andrei Broder, Stephen Cook, Ding-Zhu Du, David Eppstein, Sally Goldman, Sanjeev Khanna, Rafail Ostrovsky, Pavel Pevzner, Steven Rudich, Eli Upfal, Stephen Vavasis, Frances Yao. Program Chair Conference Chair Frances Yao Eugene Luks Sarah Mocas Dept. of Computer Science Dept. of Computer Dept. of Computer Science and Information Science Princeton University University of Oregon Portland State University Princeton, NJ 08544 Eugene, OR 97403-1202 Portland, Oregon 97207-0751 ffyao@cs.princeton.edu luks@cs.uoregon.edu sarah@cs.pdx.edu