Call for Papers

STOC 2023

At FCRC

June 20-23, 2023
Orlando, Florida

Short Abstract and Paper Registration Deadline: Friday, November 4, 2022, 4:59pm EDT.

Full Paper Submission Deadline: Monday, November 7, 2022, 4:59pm EDT.

The 55th ACM Symposium on Theory of Computing (STOC 2023), sponsored by the ACM Special Interest Group on Algorithms and Computation Theory (SIGACT), will be held in Orlando, Florida from Tuesday, June 20 to Friday, June 23. STOC will be part of FCRC.

Papers presenting new and original research on the theory of computation are sought. Typical but not exclusive topics of interest include algorithms and data structures, computational complexity, randomness in computing, algorithmic graph theory and combinatorics, analysis of Boolean functions, approximation algorithms, cryptography, computational learning theory, continuous and discrete optimization, economics and computation, parallel and distributed algorithms, quantum computing, algorithmic coding theory, computational geometry, computational applications of logic, algebraic computation, and computational and foundational aspects of areas such as machine learning, fairness, privacy, networks, data management, databases and computational biology. Papers that extend the reach of the theory of computing, or raise important problems that can benefit from theoretical investigation and analysis, are encouraged. The program committee will make every effort to consider a broad range of areas.

Submission format: Submissions should start with a title page consisting of the title of the paper and an abstract of a few paragraphs summarizing the paper's contributions. Submissions should not contain the authors' names (more on this below). There is no page limit and authors are encouraged to use the "full version" of their paper as the submission. Each 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. This part of the submission should be addressed to a broad spectrum of theoretical computer science researchers, not solely to experts in the subarea. 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, table of contents, 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.

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.

Authors are encouraged to include hyperlink cross-referencing for bibliographic entries, theorems, sections, and so on, using for example the hyperref, cleverref, or varioref packages. If helpful, a table of contents may be added on a page immediately following the title page; this will not count towards the first ten pages.

Submission pdf files should not have author names on them; author names and institution information will be uploaded separately. PC members will have access to author names if they want this information, but names should not appear on the actual submitted papers themselves. This will make it easier for PC members to remove possible unconscious biases if they want to be unaware of the identity of authors.

Recommended best practices for citations: Authors are asked to avoid "et al." in citations in favor of an equal mention of all authors' surnames. If the number of authors is large, consider writing "\cite{XYZ} show..." instead of "X et al. show". Bibliographic references should preferably be alphanumeric (e.g., the first letters of the authors' surnames (or at least the first three followed by a +) followed by year of publication, instead of just a numerical reference. If using BibTeX, this can be accomplished by using \bibliographystyle{alpha}.

PC Member Submissions: Submissions by PC members are allowed. If any of the authors of a submission is a PC member, this should be indicated in the submission form by clicking the corresponding bullet.

Conflict of Interest Policy: STOC 2023 will use the following Conflict of Interest Policy, which combines aspects suggested by SafeToC (see here) and the ACM Conflict of Interest policy. Upon submission, authors are given the opportunity to declare conflicts of interest. They should limit this declaration to the following categories:

  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/recent collaborator, or recipients of joint funding (within the last 2 years or reasonably expected within the next year) who 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. Falsely declared conflicts (i.e., do not satisfy one of the listed reasons) risk rejection without consideration of merit. 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.

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.

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 STOC.) It is expected that authors of accepted papers will make their full papers, with proofs, publicly available on arXiv, ECCC, or a similar preprint service by the camera-ready deadline.

ACM is moving to require ORCIDs for all authors, in particular for authors of conference papers starting on October 1, 2022. An ORCID is an identifier that uniquely identifies an author. It connects an author's work even if there are variations in the names used on different papers, ensuring that the author gets credit for all of their contributions. Using ORCIDs will help ACM administer the ACM OPEN program where universities get open-access publishing via a subscription, aid in identifying conflicts of interests, and support other publications processes. ORCIDs are easy to obtain; it takes less than a minute.

Prior and Simultaneous Submissions: 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 July 2023, will not be considered for acceptance at STOC 2023. The only exception to this policy are prior or simultaneous publications appearing in the Science and Nature journals. SIGACT policy does not allow simultaneous submissions of the same (or essentially the same) material to another conference with published proceedings. The program committee may consult with program chairs of other (past or future) conferences to find out about closely related submissions.

Dates and other relevant information:

Short abstract and paper registration deadline: Friday, November 4, 2022 (4:59pm EDT).

Full paper submission deadline: Monday, November 7, 2022 (4:59pm EDT).

Notification deadline: by email on or before February 6, 2023. (Note that although the STOC notification date is after the EC submission deadline, authors of rejected STOC papers will have the opportunity to submit revised papers with their STOC reviews and an author response directly into the second phase of the EC review process.)

Camera-ready versions of accepted papers: A camera-ready copy of each accepted paper is required by March 27, 2023. The format of your paper must strictly adhere to the ACM Format, and specifically the sigconf option. (LaTeX users, please use:\documentclass[sigconf,screen]{acmart}). Additional instructions will be sent directly to the authors of accepted papers.

STOC talks: Tuesday morning June 20 to Friday afternoon June 23, 2023.

Publication date: AUTHORS TAKE NOTE: The official publication date is the date the proceedings are made available in the ACM Digital Library. This date may be up to two weeks prior to the first day of your conference. The official publication date affects the deadline for any patent filings related to published work. (For those rare conferences whose proceedings are published in the ACM Digital Library after the conference is over, the official publication date remains the first day of the conference.)

Presentation of Accepted Papers: One author of each accepted paper will be expected to register and present the work in the form of a talk at the conference unless there are strong reasons not to, including international travel restrictions due to COVID-19 or impossibility to travel for all the authors of the paper. In addition, one or more authors may be expected to present the work in a poster session.

Best Paper Award: The program committee may designate up to three papers accepted to the conference as STOC Best Papers. PC member submissions are not eligible for the Best Paper award. All other submissions are automatically eligible. Rules for the award can be found at https://www.sigact.org/prizes/best_paper.html.

Danny Lewin Best Student Paper Award: A prize of $500 will be given to the author(s) of the best student authored paper (or split between more than one paper if there is a tie). A paper is eligible if all of its authors are full-time students at the time of submission. To inform the program committee about a paper's eligibility, check the appropriate box in the web form on the submission server. The list of past winners can be found at https://www.sigact.org/prizes/student.html.

Access to Proceedings: The committee intends to provide registered attendees with internet access to the Proceedings on a password-protected site that will be available from about two weeks before the conference until the end of the conference. Authors can opt out of this online distribution by contacting the program committee chair by March 15, 2023.

Student Travel Awards: SIGACT provides travel awards to students without available support, and researchers from developing countries. More information on the award process will be posted later on.

Program Committee:

Amir Abboud (Weizmann Institute of Science)
Josh Alman (Columbia University)
Andris Ambainis (University of Latvia)
Nima Anari (Stanford University)
Srinivasan Arunachalam (IBM Thomas J. Watson Research Center)
Petra Berenbrink (Universität Hamburg)
Aaron Bernstein (Rutgers University)
Aditya Bhaskara (University of Utah)
Sayan Bhattacharya (University of Warwick)
Eric Blais (University of Waterloo)
Hans Bodlaender (Utrecht University)
Adam Bouland (Stanford University)
Anne Broadbent (University of Ottawa)
Mark Bun (Boston University)
Keren Censor-Hillel (Technion)
Timothy Chan (University of Illinois at Urbana-Champaign)
Arkadev Chattopadhyay (Tata Institute of Fundamental Research)
Chandra Chekuri (University of Illinois at Urbana-Champaign)
Xue Chen (University of Science and Technology of China)
Gil Cohen (Tel Aviv University)
Dana Dachman-Soled (University of Maryland College Park)
Anindya De (University of Pennsylvania)
Shahar Dobzhinski (Weizmann Institute of Science)
Shaddin Dughmi (University of Southern California)
Vida Dujmovic (University of Ottawa)
Yuval Filmus (Technion)
Sumegha Garg (Stanford University)
Rong Ge (Duke University)
Elena Grigorescu (Purdue University)
Shuichi Hirahara (National Institute of Informatics, Japan)
Zhiyi Huang (University of Hong Kong)
Sungjin Im (University of California, Merced)
Giuseppe Italiano (LUISS University)
Ken-ichi Kawarabayashi (National Institute of Informatics, Japan)
Sanjeev Khanna (University of Pennsylvania)
Robin Kothari (Microsoft Research)
Marvin Künnemann (TU Kaiserslautern)

Rasmus Kyng (ETH Zurich)
Sophie Laplante (Université Paris Cité)
Hung Le (University of Massachusetts, Amherst)
Daniel Lokshtanov (University of California, Santa Barbara)
Sepideh Mahabadi (Microsoft Research)
Nicole Megow (Universität Bremen)
Slobodan Mitrovic (University of California, Davis)
Ankur Moitra (Massachusetts Institute of Technology)
Shay Moran (Technion and Google Research)
Christopher Musco (New York University)
Krzysztof Onak (Boston University)
Rotem Oshman (Tel Aviv University)
Prasad Raghavendra (University of California, Berkeley)
Susanna Rezende (Lund University)
Robert Robere (McGill University)
Alon Rosen (Bocconi University and Reichman University)
Ron Rothblum (Technion)
Alex Russell (University of Connecticut)
Laura Sanità (Bocconi University)
Thatchaphol Saranurak (University of Michigan)
Tselil Schramm (Stanford University)
Rocco Servedio (Columbia University) (chair)
Tasos Sidiropoulos (University of Illinois at Chicago)
Alex Slivkins (Microsoft Research)
Srikanth Srinivasan (Aarhus University)
David Steurer (ETH Zurich)
Ola Svensson (EPFL)
Chaitanya Swamy (University of Waterloo)
Madhur Tulsiani (Toyota Technological Institute at Chicago)
Christos Tzamos (University of Wisconsin-Madison)
Muthu Venkitasubramaniam (Georgetown University)
Ben Lee Volk (Reichman University)
Andreas Wiese (Technical University of Munich)
Mary Wootters (Stanford University)
Yuichi Yoshida (National Institute of Informatics, Japan)
Huacheng Yu (Princeton University)
Meirav Zehavi (Ben-Gurion University)

General Chair: Barna Saha (University of California San Diego)