56th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2015)

DoubleTree Hotel at the Berkeley Marina, Berkeley, California, October 18-20, 2015.

The 56th Annual Symposium on Foundations of Computer Science (FOCS 2015), sponsored by the IEEE Computer Society Technical Committee on Mathematical Foundations of Computing, will be held in Berkeley, California from October 18-20 (Sunday through Tuesday), with a welcome reception Saturday (October 17) evening.

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 learning theory, computational game theory, parallel and distributed algorithms, quantum computing, computational geometry, computational applications of logic, algorithmic graph theory and combinatorics, optimization, randomness in computing, approximation algorithms, parameterized complexity, algorithmic coding theory, algebraic computation, and theoretical aspects of areas such as networks, privacy, information retrieval, computational biology, and databases. Papers that broaden the reach of the theory of computing, or raise important problems that can benefit from theoretical investigation and analysis, are encouraged.

Important Dates:

Submission format:

(Please read carefully as there are some differences compared to recent FOCS conferences.)

The authors should submit an extended abstract that is at most 10 pages long, excluding the bibliography and title page (which should consist of the title of the paper; each author's name, affiliation, and email address; and an abstract of 1-2 paragraphs summarizing the paper's contributions). The page limit only applies to text, and illustrative graphic figures can extend beyond the 10 page limit. The submission should be typeset using 11-point or larger fonts, in a single-column, single-space (between lines) format with ample spacing throughout and at least 1-inch margins all around. Submissions deviating significantly from these guidelines risk rejection without consideration of their merits.

The authors should also include all the technical ideas and proofs necessary for an expert to fully verify the central claims in the paper, by supplementing the extended abstract (if necessary) with a full version. It is recommended that the full version be submitted as a separate file via the "supporting material" field of the submission server. If for some reason the authors prefer to submit a single file (say, if the full paper isn't much longer than 10 pages), the authors can supplement the extended abstract with appendices that extend beyond the main body of 10 pages.

The supplementary material will be read at the committee's discretion. The accept/reject decision will be based mainly on the 10-page extended abstract, which should be readable as a stand alone version, and contain a clear presentation of the interesting aspects of the paper, including discussion of its context and motivation, prior work, significance of the main results, and an outline of key methods and proof ideas used to achieve the main claims. To the extent possible, the extended abstract should be addressed to a broad spectrum of theoretical computer scientists, not solely to experts in the subarea.

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

Submission instructions:

Authors are required to submit their papers electronically, in PDF (without security restrictions on copying or printing). The submission server will be open to accept submissions by mid-March. Submissions will be judged solely on the basis of the version submitted by the deadline; post-deadline revisions will not be allowed.

Contacting authors:

The committee may decide to contact authors for clarifications during the review process. Please make sure your account will not mark emails from as "spam" or "low priority," so you can answer those requests in a timely manner.

On-line posting:

Authors are encouraged to post full versions of their submissions in a freely accessible on-line repository such as the arxiv, the ECCC, or the Cryptology ePrint archive. (Papers that are not written well enough for public dissemination are probably also not ready for submission to FOCS.) We expect that authors of accepted papers will make full versions of their papers, with detailed proofs, publicly available by the camera-ready deadline (this should be done in a manner consistent with the IEEE Copyright Policy).

Prior and simultaneous submission:

The conference will follow SIGACT's policy on prior publication and simultaneous submissions. Work that has been previously published in another conference proceedings or journal, or which is scheduled for publication prior to December 2015, will not be considered for acceptance at FOCS 2015. However, as exceptions, recent results announced in another journal or conference with a significantly different format, content, and audience than FOCS might be considered at the PC's discretion; in such cases authors should contact the program committee chair prior to submission. Simultaneous submission of the same (or essentially the same) abstract to FOCS 2015 and to another conference with published proceedings is not allowed. The program committee may interact with program chairs of other (past or future) conferences to find out about closely related submissions.


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.

Presentation of Accepted Papers:

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

Program Committee:

Arkadev Chattopadhyay TIFR, Mumbai
Irit Dinur Weizmann Institute
Uriel Feige Weizmann Institute
Yuval Filmus IAS, Princeton
Anupam Gupta Carnegie Mellon University
Venkatesan Guruswami (chair) Carnegie Mellon University
Aram Harrow MIT
Michael Kapralov IBM Research
Shachar Lovett University of California, San Diego
Pinyan Lu Microsoft Research
Claire Mathieu CNRS and École Normale Supérieure
Dániel Marx Hungarian Academy of Sciences
Ruta Mehta Georgia Tech
Cristopher Moore Santa Fe Institute
Huy Le Nguyen Simons Institute, UC Berkeley
Rafael Pass Cornell University
Richard Peng MIT
Seth Pettie University of Michigan
Thomas Rothvoss University of Washington
Shubhangi Saraf Rutgers University
Anastasios Sidiropoulos The Ohio State University
Santosh S. Vempala Georgia Tech
Hoeteck Wee CNRS and École Normale Supérieure
Philipp Woelfel University of Calgary

Contact Information:

General Chair: Program Committee Chair: Local Arrangements Chairs:
Rafail Ostrovsky

Venkatesan Guruswami
Carnegie Mellon University

Prasad Raghavendra
Luca Trevisan
Kristin Kane
(Simons Institute/UC Berkeley)