1999 Symposium on Foundations of Computer Science

New York City, NY

October 17-19, 1999

Additional FOCS '99 Information: See

The Fortieth Annual Symposium on Foundations of Computer Science (FOCS), sponsored by the IEEE Computer Society Technical Committee on Mathematical Foundations of Computing, will be held in New York City, NY on October 17-19, 1999. 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, computational algebra and geometry, algorithmic graph theory and combinatorics, cryptography, biological computing, computational biology, databases, machine learning, applications of logic, parallel and distributed computation, quantum computation, and probabilistic computation.

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 electronic address, followed by a one-paragraph summary of the results to be presented. A scholarly exposition of ideas, techniques, and results should follow, 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 Authors who do not wish to submit electronically must submit seventeen (17) printed copies (double-sided preferred) of an extended abstract, together with a cover letter to the FOCS program chair (address below). To facilitate notification, authors submitting printed copies should also send an e-mail to indicating that they are submitting in this manner. The abstract, in either form, must be received by 17:59 PDT April 23, 1999. This is a firm deadline; 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.


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


During the conference, some time will be reserved for tutorials that focus on new developments and research opportunities within a specific topic of interest to the community, given by leading researchers in the area. Proposals for tutorials as well as speaker and topic nominations should be sent to the program chair.

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 in the submission letter. The program committee may decline to make the award, or may split it among several papers.

Committee Members:

Susanne Albers (Max Planck Institute Saarbrucken),
Eric Allender (Rutgers University),
James Aspnes (Yale University),
Yair Bartal (Lucent Bell Labs),
Paul Beame (University of Washington),
Andrei Broder (Compaq Systems Research Center),
Nader Bshouty (Technion and University of Calgary),
Oded Goldreich (Weizmann Institute),
Ming Li (University of Waterloo),
Joseph Mitchell (SUNY Stonybrook),
Michael Mitzenmacher (Harvard University),
Dana Randall (Georgia Tech),
Satish Rao (NEC Research Institute),
David Shmoys (Cornell University),
Peter Shor (AT&T Research),
Luca Trevisan (Columbia University)

Program Chair:

Paul Beame
Computer Science and Engineering
University of Washington
Seattle, WA 98195-2350

Local Arrangements Chair:

Piotr Berman
324 Pond Laboratory
Computer Science and Engineering
Penn State University
University Park, PA 16802

FOCS '99 Information: See