50th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2009)
http://www.cs.yale.edu/focs09

Atlanta, GA
October 24-27, 2009

The 50th Annual Symposium on Foundations of Computer Science (FOCS2009), sponsored by the IEEE Computer Society Technical Committee on Mathematical Foundations of Computing, will be held in at the Renaissance Atlanta Hotel Downtown in Atlanta, GA, October 24-27, 2009. Papers presenting new and original research on theory of computation are sought. Typical but not exclusive topics of interest include: algorithms and data structures, computational complexity, cryptography, computational geometry, computational game theory, algorithmic graph theory and combinatorics, optimization, randomness in computing, parallel and distributed computing, machine learning, applications of logic, algorithmic algebra and coding theory, theoretical aspects of databases, information retrieval, networks, computational biology, robotics, and quantum computing. Papers that broaden the reach of theory, or raise important problems that can benefit from theoretical investigation and analysis, are encouraged.


Important Dates:

Submission deadline:

Extended abstract must be received by April 2, 2009 (18:59 EDT).
Brief description must be received by April 9, 2009 (18:59 EDT).

Notification:

Accept/reject decisions will be made by June 25, 2009.

Final versions:

Final versions of accepted papers due Aug 7, 2009.

Submission format:
Authors should submit an extended abstract, as well as a brief informal description of their paper. All submitted materials will be treated as confidential, and will only be disclosed to the committee and their chosen sub-referees.

Extended abstract:

The extended abstract should contain a scholarly exposition of ideas, techniques, and results, including motivation and a clear comparison with related work. The body of the extended abstract should not exceed ten (10) letter-sized pages (not including the bibliography, figures, and appendix) using 11-point or larger fonts, in a single-column format with ample spacing and 1-inch margins all around. Authors are expected to include all the ideas necessary for an expert to verify the central claims in the paper. If necessary, proofs may appear in a clearly marked appendix. However, any material not included in the body may be ignored at the discretion of the Program Committee. Abstracts deviating significantly from these guidelines risk rejection without consideration of their merits.

The extended abstract should be self-contained, and not rely on the brief description.

Brief description:

Ideally, the brief description should be an informal description of the most interesting ideas in the paper. The contents may range all the way from a discussion of the conceptual contributions of the paper, to a sketch of the key ideas in the proof of the simplest non-trivial statement of the main result. In other words, the brief description should provide the same understanding conveyed in a brief conversation or presentation. The brief description should be no more than two pages, using the same font size, margins and spacing as the extended abstract. It may replicate material from the extended abstract, or even be a copy of its first two pages. But, it must not contain any technical material not present in the extended abstract.

Submission instructions:

Papers must be submitted electronically.
Detailed instructions may be found at http://www.cs.yale.edu/focs09/instr.html

Simultaneous submission:

Abstract material that has been previously published in another conference proceedings or journal, or which is scheduled for publication prior to December 2009, will not be considered for acceptance at FOCS 2009. Simultaneous submission of the same (or essentially the same) abstract to FOCS 2009 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 June 25, 2009. A final copy of each accepted paper is required by Aug 7, 2009. Again this is 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.



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 by by email to the program chair at spielman@cs.yale.edu. The program committee may decline to make the award, or may split it among several papers.



Program Committee:

Sanjeev Arora, Princeton University
Maria Florina Balcan, Microsoft Research
Boaz Barak, Princeton University
Mark Braverman, Microsoft Research
Amit Chakrabarti, Dartmouth College
Ken Clarkson, IBM Almaden Research Center
Alon Efrat, University of Arizona
Martin Fürer, Pennsylvania State University, visiting University of Zürich
Anna Gilbert, University of Michigan
Phil Klein, Brown University
Ming Li, University of Waterloo
Mihai Pătraşcu, IBM Almaden Research Center
Dana Ron, Tel-Aviv University
Tim Roughgarden, Stanford University
Daniel Spielman (Chair), Yale University
Mario Szegedy, Rutgers University
Kunal Talwar, Microsoft Research
Eli Upfal, Brown University
Umesh Vazirani, University of California at Berkeley
Vijay Vazirani, Georgia Institute of Technology
Berthold Vöcking, RWTH Aachen University

Local Arrangements:
Information about local arrangements can be obtained from the Local Arrangements Web page at http://www.cc.gatech.edu/focs2009. Questions may be addressed by contacting the Local Arrangements Chairs, Milena Mihail and Prasad Tetali by email to focs2009@cc.gatech.edu or focs2009.local@gmail.com.