Call for Papers

62nd FOCS

February 7-10, 2022

Paper Registration Deadline (Title and abstract):

5 pm EDT, May 31, 2021

Paper Submission Deadline:

5 pm EDT, June 3, 2021

The 62nd Annual Symposium on Foundations of Computer Science (FOCS), sponsored by the IEEE Computer Society Technical Committee on Mathematical Foundations of Computing, will be held in Boulder, Colorado on February 7-10, 2022.

The conference seeks papers presenting new and original research on the theory of computation. Typical but not exclusive topics of interest include:

  • Algorithms and data structures
  • Computational complexity 
  • Cryptography
  • Computational learning theory
  • Continuous and discrete optimization
  • Economics and computation
  • Parallel and distributed algorithms
  • Quantum computing
  • Computational geometry
  • Computational applications of logic
  • Algorithmic graph theory and combinatorics
  • Randomness in computing
  • Approximation algorithms
  • Algorithmic coding theory
  • Algebraic computation
  • Computational and foundational aspects of areas such as machine learning, fairness, privacy, networks, data management, databases, and computational biology

We especially encourage papers that broaden the reach of the theory of computing, make foundational connections to other areas, or raise important problems and demonstrate that they can benefit from theoretical investigation and analysis. 

Ethics: FOCS is an IEEE conference and as such, we will review papers in alignment with the IEEE ethics guidelines. Authors are encouraged to reflect on these guidelines in shaping their work, dissemination, and submission.

Important Dates:

  • Pre-registration Deadline (including titles and abstracts): 5 pm, May 31, 2021.  
  • Paper Submission Deadline: 5 pm EDT, June 3, 2021.  
  • Notification: by end of August 2021. (Note that this is after SODA submission deadline.)
  • Final versions of accepted papers due: TBD

Submission format:

Submissions should start with a title page consisting 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.

There is no page limit and the authors are encouraged to use a full version of their paper as the submission. The submission must contain within its first ten pages (after the title page) a clear presentation of the merits of the paper, including a discussion of its importance, its conceptual and technical novelty, connections to related and prior work, and an outline of key technical ideas and methods used to achieve the main claims. This part of the submission should be addressed to a broad spectrum of theoretical computer scientists, not solely to experts in the subarea.

The submission should include proofs of all central claims. Although there is no bound on the length of a submission, material other than the title page, references, and the first ten pages will be read at the committee’s discretion. Authors are encouraged to put the references at the very end of the submission.

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 margins of at least 1-inch 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. In addition, the program committee may consult with journal editors and program chairs of other conferences about controversial issues such as parallel submissions.

Submission instructions:

Authors are required to submit their papers electronically, in PDF (without security restrictions on copying or printing). Submissions will be judged solely on the basis of the paper submitted by the deadline; post-deadline revisions will not be allowed.

When you register your submission, you will, among other things, have to register an abstract in plain text. Title and abstract entered by the pre-registration deadline will be considered near-final and will be used for PC bidding. This abstract plays a prominent role in the evaluation process, e.g., it is displayed when the paper is discussed. It is therefore advised that you make sure that the plain text abstract reads well.

We will be implementing the same conflict of interest policy as in the previous years. Click here for details. As in previous years, submissions by PC members will not be accepted.

Submit your paper at the 62nd FOCS Submission Server here.

Online posting:

Authors are encouraged to post full versions of their submissions in a freely accessible online 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 proofs, available before the conference begins. (This should be done in a manner consistent with the IEEE Copyright Policy.)

Prior and simultaneous submission:

Work that has been previously published in another conference proceedings or journal, or which has a chance of being published before the end of the conference, will not be considered for acceptance at the 62nd FOCS. Simultaneous submission of the same (or essentially the same) extended abstract to the 62nd FOCS and to another conference with published proceedings is not allowed. The only exceptions to this policy are prior or simultaneous publications appearing in the journals Science and Nature. If there are other submissions/publications with substantial overlap, then this should be disclosed on the title page.

Awards:

The Machtey award will be given to the best paper or papers written solely by one or more students. A paper is eligible if all authors are full-time students at the time of submission. Eligibility 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 may 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:

Alex Andoni Columbia
Pranjal Awasthi Google
Yossi Azar Tel Aviv University
Arnab Bhattacharyya National University of Singapore
Zvika Brakerski Weizmann Institute of Science
Anindya De University of Pennsylvania
Uriel Feige Weizmann Institute of Science
Ankit Garg Microsoft Research India
Anna Gilbert Yale
David Gosset University of Waterloo
Joshua Grochow University of Colorado Boulder
Johan Håstad KTH Royal Institute of Technology
Daniel Hsu Columbia
Prateek Jain Google India
Russell Impagliazzo UC San Diego
Pritish Kamath Toyota Technological Institute at Chicago
Anna Karlin University of Washington
Tali Kaufman Bar-Ilan University
Ravi Kumar Google
Silvio Lattanzi Google Zurich
Yin Tat Lee University of Washington
Lorenzo Orecchia University of Chicago
Merav Parter Weizmann Institute of Science
R. Ravi Carnegie Mellon University
Susanna Rezende Czech Academy of Sciences
Noga Ron-Zewi University of Haifa
Aviad Rubinstein Stanford
Barna Saha UC Berkeley
Daniel Spielman Yale
Piyush Srivastava Tata Institute of Fundamental Research
Daniel Stefankovic University of Rochester
László Végh London School of Economics
Cynthia Vinzant North Carolina State University and IAS
Nisheeth Vishnoi (Chair) Yale
Amir Yehudayoff Technion – Israel Institute of Technology