FOCS 2012 - 2012 IEEE 53rd Annual Symposium on Foundations of Computer Science (FOCS)

The 53rd Annual Symposium on Foundations of Computer Science (FOCS 2012), sponsored by the IEEE Computer Society Technical Committee on Mathematical Foundations of Computing, will be held at the Hotel Zozo in Palm Springs, CA, October 20-23, 2012.
A series of tutorial presentations will be given. Papers presenting new and original research on the theory of computation are sought, including papers that broaden the reach of computer science theory, or raise important problems.
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.
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 full proofs of the central claims in the paper. If necessary, these 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:
The brief description should be no more than two pages, using the same font size, margins and spacing as the extended abstract. It should contain an informal description of the paper. It may contain an overview of the main results, concepts, or ideas introduced in the paper. It should provide the same understanding conveyed in a brief conversation or presentation. 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.
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
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