24-27 October 2009
Atlanta GA, U.S.A.
CALL FOR PAPERS 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 through the electronic submission process or by email to the program chair. 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 Frer, Pennsylvania State University, visiting University of Zr ich Anna Gilbert, University of Michigan Phil Klein, Brown University Ming Li, University of Waterloo Mihai Pa(tras,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 Vcking, 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.