FOCS 2011
52nd Annual IEEE Symposium on
Foundations of Computer Science

October 22-25, 2011
Palm Springs, California

Call for papers


How to submit

Accepted papers with abstracts

FOCS 2011 Main Page


52nd Annual IEEE Symposium on Foundations of Computer Science (FOCS 2011)

Palm Springs, California, October 23-25, 2011.

The 52nd Annual Symposium on Foundations of Computer Science (FOCS2011), sponsored by the IEEE Computer Society Technical Committee on Mathematical Foundations of Computing, will be held at Hotel Zoso in Palm Springs, California on October 23-25 (Sunday through Tuesday). A series of tutorial presentations will be given on Saturday, October 22nd.

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, privacy, 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 computer science theory, or raise important problems that can benefit from theoretical investigation and analysis, are encouraged.

Important Dates:

  • Submission deadline: 7pm PST, April 13, 2011.
  • Notification: July 1st, 2011.
  • Final version of accepted papers due: August 15, 2011.

Submission format:

Authors should submit an extended abstract, which should contain a scholarly exposition of ideas, techniques, and results, including motivation and a clear comparison with related work. Authors are expected to include all ideas necessary for an expert to fully verify the central claims in the paper. There is no bound on the length of a submission, but a submission must contain within its first ten pages a clear presentation of the merits of the paper, including discussion of its importance, prior work, and an outline (similar to a brief oral presentation) of key technical ideas and methods used to achieve the main claims. Material other than the abstract, references and the first ten pages may be considered as supplementary and will be read at the committee's discretion.

The extended abstract should be typeset using 11-point or larger fonts, in a single-column, single-space (between lines) format with ample spacing throughout and 1-inch margins all around. Submissions deviating significantly from these guidelines risk rejection without consideration of their merits.

All submissions will be treated as confidential, and will only be disclosed to the committee and their chosen sub-referees.

While there is no page limit for the submissions, there will be a page limit for the proceedings version. Authors are strongly encouraged to post a full version of their accepted papers on a freely accessible forum such as, for example, the arxiv, the ECCC, or the Cryptology ePrint archive.

Submission instructions:

Authors are required to submit their extended abstracts electronically, in PDF (without security restrictions on copying or printing). See for electronic submission instructions. Submissions will be judged solely on the basis of the extended abstract submitted by the deadline; postdeadline revisions will not be allowed.

Simultaneous submission:

Abstract material that has been previously published in another conference proceedings or journal, or which is scheduled for publication prior to December 2011, will not be considered for acceptance at FOCS 2011. Simultaneous submission of the same (or essentially the same) abstract to FOCS 2011 and to another conference with published proceedings or journal is not allowed.


The Machtey award will be given to the best paper or papers 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 at the time of submission. All submissions are eligible for the Best Paper award. The committee may decide to split the awards between multiple papers, or to decline to make an award.

Program Committee:

Nir Ailon Technion
Eli Ben-Sasson Technion
Serge Fehr CWI Amsterdam
Juan A. Garay AT&T Labs--Research
Russell Impagliazzo IAS and University of California, San Diego
Sandy Irani University of California, Irvine
Kamal Jain Microsoft Research, Redmond
Stefano Leonardi Sapienza University of Rome
Richard Lipton Georgia Tech
Claire Mathieu Brown University
Dieter van Melkebeek University of Wisconsin, Madison
Ashwin Nayak University of Waterloo and Perimeter Institute
Rafail Ostrovsky (chair) University of California, Los Angeles
Boaz Patt-Shamir MIT and Tel Aviv University
Tim Roughgarden Stanford University
Rocco Servedio Columbia University
Adam Smith Pennsylvania State University
Kunal Talwar Microsoft Research, Silicon Valley
Chris Umans Caltech
Chee Keng Yap New York University
Lisa Zhang Alcatel-Lucent Bell Labs

Contact Information:

General Chair: Program Committe Chair: Local Arrangements Chairs:
Paul Beame
University of

Rafail Ostrovsky
UCLA. Contact email:

Marek Chrobak,
Neal Young,
University of California at Riverside.

Presentation of Accepted Papers:

One author of each accepted paper will be expected to present the work at the conference.