Overview

The 63rd Annual Symposium on Foundations of Computer Science (FOCS 2022), sponsored by the IEEE Computer Society Technical Committee on Mathematical Foundations of Computing, will be held in Denver, Colorado October 31—November 3, 2022.

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, foundations of machine learning, parallel and distributed algorithms, quantum computing, computational geometry, computational applications of logic, algorithmic graph theory and combinatorics, optimization, randomness in computing, approximation algorithms, 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 deadline	April 4, 2022 at 16:59 PDT
Preliminary reviews released to authors	June 14, 2022
Author rebuttals due	June 19, 2022 at 16:59 PDT
Notification	July 4, 2022
Conference	October 31 — November 3, 2022

Submission format

Submissions should start with a title page consisting of the title of the paper, and an abstract of 1-2 paragraphs summarizing the paper's contributions. FOCS 2022 will use double-blind reviewing, and as such submissions should not reveal the identity of the authors in any way. In particular, authors' names, affiliations, and email addresses should not appear at the beginning or in the body of the submission, and authors should ensure that any references to their own related work are in the third person. There is no page limit and authors are encouraged to use the "full version" of their paper as the submission. The submission should contain within the initial ten pages following the title page a clear presentation of the merits of the paper, including a discussion of the paper's importance within the context of prior work and a description of the key technical and conceptual ideas used to achieve its main claims. The submission should be addressed to a broad spectrum of theoretical computer science researchers. Proofs must be provided which can enable the main mathematical claims of the paper to be fully verified. Although there is no bound on the length of a submission, material other than the abstract, 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 1-inch margins all around, on letter-size (8 1/2 x 11 inch) paper. Submissions deviating significantly from these guidelines risk rejection without consideration of their merits.

Submissions by PC members are allowed but will be measured against a higher bar. If any of the authors of a submission is a PC member, this should be indicated in the submission form by checking the corresponding box.

Rebuttals

Preliminary reviews will be released to authors during the review process, and authors will have approximately five days to write and submit rebuttals (see important dates above). Rebuttals should be used to address factually incorrect statements or major misunderstandings in reviews, or to address questions related to correctness. It is perfectly acceptable, and encouraged, to not submit a rebuttal outside of such circumstances.

Submission instructions

Authors are required to submit their papers electronically, in PDF (without security restrictions on copying or printing). The submission server is now open. At the bottom of the submission page there is space to include potential conflicts of interest, to help manage the double-blind review process. This information can only be seen by the program committee chair and thus cannot be used by the rest of the program committee to deanonymize authors. Please only include conflicts of interest as defined by SafeToC:

1. Family member or close friend.
2. Ph.D. advisor or advisee (no time limit), or postdoctoral or undergraduate mentor or mentee within the past five years.
3. Person with the same affiliation.
4. Person involved in an alleged incident of harassment. (It is not required that the incident be reported.)
5. Reviewer owes author a favor (e.g., recently requested a reference letter).
6. Frequent or recent collaborator (within the last 2 years) whom you believe cannot objectively review your work.

If you are unsure about a conflict in which a reviewer may have positive bias towards your paper, we recommend erring on the side of not declaring it since PC members and sub-reviewers will be also asked if they feel that they can fairly evaluate your paper. If an author believes that they have a valid reason for a conflict of interest not listed above, then he or she can contact the PC chair or any ToC advocate affiliated with this conference directly. Note that if the program chair has reason to doubt the validity of the claim of conflict of interest, then he/she may request that a ToC advocate confidentially verify the reason for the conflict. If authors are uncertain, they are encouraged to email the PC chair or a ToC advocate. The submission software asks for conflicts with PC members, and in addition contains a text form in which one can declare additional conflicts.

Authors are encouraged to also make full versions of their submissions freely accessible in an online repository such as the arXiv, 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.) It is expected that authors of accepted papers will make their full papers, with proofs, publicly available by the camera-ready deadline.

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 2022, will not be considered for acceptance at FOCS 2022. Simultaneous submission of the same (or essentially the same) abstract to FOCS 2022 and to another conference with published proceedings or journal is not allowed. The program committee may interact with program chairs of other (past or future) conferences to find out about closely related submissions. Notwithstanding the above, works that were previously published or announced in another journal or conference with a significantly different format, content, and audience than FOCS might still be considered at the PC's discretion; in such cases authors should contact the program chair prior to submission.

Awards

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. Authors are expected to contact the program chair before submission in case insufficient travel funds could prevent them from attending the conference.

Program Committee

Josh Alman	Columbia University
Anurag Anshu	Harvard University
Nir Bitansky	Tel Aviv University
Keren Censor-Hillel	Technion
Amit Chakrabarti	Dartmouth College
Lijie Chen	MIT
Xi Chen	Columbia University
Sitan Chen	UC Berkeley
Kai-Min Chung	Institute of Information Science, Academia Sinica
Daniel Dadush	CWI
Ilias Diakonikolas	University of Wisconsin, Madison
Sanjam Garg	UC Berkeley / NTT Research
Ashish Goel	Stanford University
Alexander Golovnev	Georgetown University
Piotr Indyk	MIT
Rahul Jain	National University of Singapore
Jonathan Kelner	MIT
James Lee	University of Washington
Jason Li	UC Berkeley
Nancy Lynch	MIT
David Mount	University of Maryland
Chris Musco	NYU
Jelani Nelson	UC Berkeley (chair)
Huy Le Nguyen	Northeastern University
Andrej Risteski	Carnegie Mellon University
Shubhangi Saraf	University of Toronto
Thomas Steinke	Google
Nike Sun	MIT
Vera Traub	ETH Zurich
Emanuele Viola	Northeastern University
Yuichi Yoshida	National Institute of Informatics

Organizers

General Chair	Shang-Hua Teng, USC
Program Chair	Jelani Nelson, UC Berkeley, focs2022chair@gmail.com
Finance Chair	Rong Ge, Duke
Local Arrangements Chair	Alexandra Kolla, UC Santa Cruz/University of Colorado Boulder
Workshop Co-chairs	Vincent Cohen-Addad (Google), Henry Yuen (Columbia)