CALL FOR PAPERS            

41st Annual IEEE Symposium on Foundations of Computer Science
http://www.cs.cmu.edu/~FOCS2000

Redondo Beach, CA
November 12-14, 2000 The 41st Annual Symposium on Foundations of Computer Science (FOCS 2000), sponsored by the IEEE Computer Society Technical Committee on Mathematical Foundations of Computing, will be held in Redondo Beach, CA on November 12-14, 2000. Papers presenting original research on theoretical aspects of computer science are sought. Typical but not exclusive topics of interest include: algorithms and data structures, computational complexity, cryptography, computational geometry, algorithmic graph theory and combinatorics, parallel and distributed computing, computational biology, machine learning, databases, applications of logic, quantum computation, online algorithms, algorithmic coding theory, (de)randomization, and robotics. More information on the conference will be available at http://www.cs.cmu.edu/~FOCS2000.

Submission Deadline: Friday April 28, 2000 (must be RECEIVED by 17:59 EDT).

Abstract format: Authors should submit an extended abstract (not a full paper). The submission should contain a scholarly exposition of ideas, techniques, and results, including motivation and a clear comparison with related work. The length should not exceed ten (10) letter-sized pages (not including the bibliography, and using 11 point or larger font, with ample spacing and margins all around). More details may be given in an appendix, but any material beyond the 10-page limit may be ignored 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 the web site given above. Authors who do not wish to submit electronically must submit fifteen printed copies (double-sided preferred) of an extended abstract, together with a cover letter to:

Avrim Blum, FOCS-2000 Program Chair

Department of Computer Science

Carnegie Mellon University

Pittsburgh, PA 15213-3891 USA

To facilitate notification, authors submitting printed copies should also send an e-mail to avrim@cs.cmu.edu indicating that they are submitting in this manner. The abstract, in either form, MUST be received by 17:59 EDT April 28, 2000. Late submissions will be rejected. Simultaneous submission of the same (or essentially the same) abstract to FOCS and to another conference with published proceedings is not allowed.

Notification: Authors will be sent notification of acceptance or rejection by e-mail on or before July 3, 2000. A final copy of each accepted paper is required by August 31, 2000. This is again a firm deadline. An author of each accepted paper must attend the Symposium and present the paper, or make arrangements to have it presented.

Machtey award: This prize will be given to the best paper written solely by one or more students. An abstract is eligible if all authors are full-time students at the time of submission. This should be indicated to the electronic submission server. The program committee may decline to make the award, or may split it among several papers.

Program Committee:

Sanjeev Arora (Princeton) R. Ravi (Carnegie Mellon)

Avrim Blum (Carnegie Mellon) Leonard Schulman (Georgia Tech & Caltech)

Faith Fich (Toronto) Michael Sipser (MIT)

Leslie Ann Goldberg (Warwick) Mario Szegedy (Institute for Advanced Studies)

Michael Goodrich (Johns Hopkins) Umesh Vazirani (UC Berkeley)

Monika Henzinger (Google) David Williamson (IBM Watson)

Joe Kilian (NECI) David Zuckerman (UT Austin & UC Berkeley) Yishay Mansour (Tel-Aviv)

Information about local arrangements can be obtained from the Local Arrangements Chairs: Marek Chrobak and Tao Jiang (marek@cs.ucr.edu, jiang@cs.ucr.edu).