Theoretical computer science has produced a remarkable wealth of beautiful ideas with tremendous impact on computer science and beyond. Some of the most powerful contributions, such as P versus NP, pseudo randomness, zero-knowledge proofs, PCP, quantum computers, boosting, etc, represent not only major technical breakthroughs, but also distill fundamental computational concepts and make deep connections between different fields and areas. STOC and FOCS played a critical role in nurturing these connections when the field was smaller and more intimate, by providing a forum where essential new ideas could be distilled, rapidly communicated, assimilated, discussed and reinterpreted. With the growth of the theoretical computer science and the corresponding deluge of information, what is the most effective role that a conference can play in facilitating the type of dialog necessary for future powerful contributions to the field? The quest of ITCS is to embody the answer to this question.
Dialog and discussions between sub-areas of ITCS are facilitated by organizing ITCS as a single track conference, with "Chair rants" helping provide the context for each session. Moreover, submissions, refereeing and presentations emphasize the I in ITCS: new concepts or models, new lines of inquiry, new techniques or novel use of existing techniques, and new connections between areas. Communication is further aided by rapid dissemination (four months from submission to conference), and free access via electronic proceedings.
The 12th Innovations in Theoretical Computer Science (ITCS) conference will be held online from January 6-8, 2021. More detailed information about the format of the conference will be posted after the author notifications are sent.
ITCS seeks to promote research that carries a strong conceptual message (e.g., introducing a new concept, model or understanding, opening a new line of inquiry within traditional or interdisciplinary areas, introducing new mathematical techniques and methodologies, or new applications of known techniques). ITCS welcomes both conceptual and technical contributions whose contents will advance and inspire the greater theory community.
Notification to authors:
September 8, 2020 (05:59pm PDT)
November 1, 2020
January 6-8, 2021
Andris Ambainis, University of Latvia
Nima Anari, Stanford
Elette Boyle, IDC Herzliya
Mark Braverman, Princeton
Sebastien Bubeck, Microsoft Research
Claire Mathieu, CNRS, Paris
Edith Cohen, Google
Anindya De, University of Pennsylania
Uriel Feige, Weizmann Institute
Kira Goldner, Columbia
Monika Henzinger, University of Vienna
Maurice Herlihy, Brown
Sam Hopkins, UC Berkeley and MIT
Tali Kaufman, Bar-Ilan University
Adam Klivans, UT Austin
Gillat Kol, Princeton
Alexandra Kolla, University of Colorado, Boulder
Lap Chi Lau, University of Waterloo
James R. Lee, University of Washington (chair)
Jamie Morgenstern, University of Washington
Anand Natajaran, MIT
Alantha Newman, Université Grenoble Alpes
Lorenzo Orecchia, University of Chicago
Debmalya Panigrahi, Duke University
Richard Peng, Georgia Tech
Ron Rothblum, Technion
Aviad Rubinstein, Stanford
Tselil Schramm, Stanford
Leonard Schulman, California Institute of Technology
Anastasios Sidiropoulos, University of Illinois at Chicago
Nikhil Srivastava, UC Berkeley
Ola Svensson, EPFL
Avishay Tal, UC Berkeley
Luca Trevisan, Bocconi University
Jan Vondrak, Stanford
Matt Weinberg, Princeton
Amir Yehudayoff, Technion
Mark Zhandry, Princeton and NTT Research
Authors should upload a PDF of the paper to hotcrp using the following link: https://itcs2021.hotcrp.com. The font size should be at least 11 point and the paper should be single column. Beyond these, there are no formatting requirements. Authors are required to submit a COI declaration upon submission.
Submissions should not have the authors' names on them. Instead, author and institution information is to be uploaded separately. PC members will still be able to access author names in the reviewing process if they feel they need to; the intent of this procedure is to make it easier for PC members to remove unconscious biases. You are free (and encouraged) to post your paper on your web page, the arXiv, etc.
Authors should strive to make their paper accessible not only to experts in their subarea, but also to the theory community at large. The submission should include proofs of all central claims. In addition, it is recommended that the paper contain, within the first 10 pages, a concise and clear presentation of the merits of the paper, including a discussion of its significance, innovations, and place within (or outside) of our field's scope and literature. The committee will put a premium on writing that conveys clearly, in as simple and straightforward a manner as possible, what the paper accomplishes.
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.
Results published/presented/submitted at another archival conference will not be considered for ITCS. Simultaneous submission to ITCS and to a journal is allowed. Papers accepted to ITCS should not be submitted to any other archival conferences.
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. We expect that authors of accepted papers will make full versions of their papers, with proofs, available before the conference begins.
A talk accompanying each accepted paper will be streamed live during the conference by one or more of the authors (details forthcoming). There will be opportunities for additional extended presentations and posting of background material that participants may view prior to the talk.
Conference attendees are expected to abide by an anti-harassment code of conduct.
The list of accepted papers is available here.
Participants near to graduation (on either side) will be given an opportunity to present their results, research, plans, personality, and so on during the "Graduating bits" session. This is one of the important traditions of ITCS, and not to be missed!
Typical accepted papers will be published by LIPIcs in the electronic proceedings of the conference. To accommodate the publishing traditions of different fields, authors of accepted papers can ask the PC chair to have only a one page abstract of the paper appear in the proceedings, along with a URL pointing to the PDF of the full paper on an online archive.
The committee may award a "best student paper" award.