Call for Papers

The 4th Innovations in Theoretical Computer Science (ITCS) conference, sponsored by the ACM Special Interest Group on Algorithms and Computation Theory (SIGACT), will be held in Berkeley, California, January 10-12, 2013.

ITCS (previously known as ICS) seeks to promote research that carries a strong conceptual message (e.g., introducing a new concept or model, opening a new line of inquiry within traditional or cross-interdisciplinary areas, or introducing new techniques or new applications of known techniques). ITCS welcomes all submissions, whether aligned with current theory of computation research directions or deviating from them.

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. A submission must contain within its first ten pages a clear presentation of the merits of the paper, including discussion of its importance, prior work, and an outline (similar to a brief oral presentation) of key technical ideas and methods used to achieve the main claims. There is no bound on the length of a submission, but material other than the abstract, references, and the first ten pages may be considered as supplementary and 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 include all of the ideas necessary for an expert to verify fully the central claims in the paper. Finally, the submission should be addressed to a broad spectrum of theoretical computer scientists, not solely to experts in the subarea.

The extended abstract 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. 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.

Submission Instructions

Authors are required to submit their papers electronically, in PDF (without security restrictions on copying or printing). The submission server is accessible through the following link:

Simultaneous Submissions and Prior Publications

Papers which have been previously presented at a CS conference with published proceedings, or are currently under submission to another such conference, will not be considered for acceptance in ITCS 2013. On the other hand, authors are welcome to submit a paper even if the same paper (or a paper with substantial overlap) has previously appeared in a form other than a CS conference with published proceedings, e.g. a journal, or has already been accepted to any such venue. In such cases the prior publication category must be selected when submitting the paper, and the title page must clearly indicate where the paper (or substantially overlapping paper) has previously appeared or been accepted. In accordance with SIGACT's policy on prior publications, such papers will not be published in the proceedings but will instead be summarized by a one-page abstract accompanied by a bibliographic citation to the published or accepted version of the paper. The program committee reserves the right to apply a higher standard when evaluating such papers.

Questions about this policy should be directed to

Working Papers

To accommodate the publishing traditions of different fields, authors submitting work that is under review or nearly ready for journal review may choose to designate their submission as a working paper, meaning that only a one page abstract will appear in the proceedings, along with a URL pointing to the full paper and guaranteed to be reliable for at least two years. We prefer open access; however, the link can reference a publisher who takes copyright and limits access. Working papers and regular papers are treated equivalently from the standpoint of the conference review process, and they are subject to the same rules regarding formatting, prior publication, and simultaneous submission. The title page should state clearly that the submission is a working paper.

Important Dates

Extended Abstract Submission:       Monday August 13, 2012 at 23:59pm US PDT.
Notification to authors: Monday October 22, 2012 at 23:59pm US PDT.
Camera ready papers due: Thursday, November 25, 2012, at 23:59pm US PDT.
Conference dates: January 10 - 12, 2013.

Best Student Paper Award

We are happy to announce a best paper award for papers all of whose authors are full-time students at the time of submission. Student authors who are interested in being considered for this award should notify the chair of their student status and eligibility for the award.

Steering Committee

Sanjeev Arora, Manuel Blum, Bernard Chazelle, Oded Goldreich, Shafi Goldwasser, Richard Karp, Ueli Maurer, Silvio Micali, Peter Bro Miltersen, Christos Papadimitriou, Michael Rabin, Madhu Sudan, Leslie Valiant, Umesh Vazirani, Avi Wigderson, and Andy Yao.

Program Committee

Mark Braverman           Princeton
Shuchi Chawla University of Wisconsin
Julia Chuzhoy TTI-Chicago
Yevgeniy Dodis New York University
Andrew Drucker MIT and IAS
Uriel Feige Weizmann Institute
Ravi Kannan Microsoft Research India
Robert Kleinberg (Chair) Cornell
Eyal Kushilevitz Technion
S. Muthukrishnan Rutgers
Ronitt Rubinfeld MIT and Tel Aviv University
Atri Rudra University at Buffalo
Adam Smith Pennsylvania State University
Santosh Vempala Georgia Tech
Andrew Yao Tsinghua

Organizing Committee

Satish Rao              U.C. Berkeley
Christos Papadimitriou U.C. Berkeley
Umesh Vazirani U.C. Berkeley


The conference website is at

Contact Information

Inquiries should be addressed to