The 45th ACM Symposium on Theory of Computing (STOC 2013), sponsored by the ACM Special Interest Group on Algorithms and Computation Theory (SIGACT), will be held in Palo Alto, CA from Saturday, June 1 to Tuesday, June 4, 2013. Submissions presenting original research on the theory of computation are sought. Topics of interest include but are not limited to: algorithms and data structures, computational complexity, algorithmic coding theory, algorithmic graph theory and combinatorics, approximation algorithms, computational geometry, computational learning theory, cryptography, economics and computation, optimization, parallel and distributed algorithms, quantum computing, randomness in computing, and theoretical aspects of other CS-research areas, e.g., computational science, databases, information retrieval, networking, privacy, and security.

Program Chair: Joan Feigenbaum (Yale University)

Program Committee: STOC 2013 will have a very large Program Committee (PC), each member of which will evaluate a modest number of submissions in depth, and a smaller Executive Committee (EC) to oversee the reviewing process. PC members are allowed to submit papers, but EC members are not. A complete list of PC members can be found on the conference website. The EC members are Boaz Barak (Microsoft Research, New England), Irit Dinur (Weizmann Institute), Joan Feigenbaum (Yale University), Leslie Goldberg (University of Liverpool), Giuseppe F. Italiano (University of Rome “Tor Vergata”), Sampath Kannan (University of Pennsylvania), Neeraj Kayal (Microsoft Research, India), Michael Mitzenmacher (Harvard University), and Miklos Santha (CNRS, University of Paris Diderot).

Submission format: Authors are required to submit an extended abstract of at most 10 pages, including the bibliography, in (two-column) ACM-Proceedings format. All instructions, including latex templates, needed to produce a PDF file in the required format are available here. Note that, in a break from STOC tradition, STOC 2013 is using the same format and length restriction for submissions and proceedings contributions. Submissions that do not conform to these requirements will not be considered for STOC 2013.

Submission instructions: Authors are required to submit their extended abstracts electronically, in PDF, without restrictions on copying or printing. The submission server will be available on or before Friday, October 5, 2012, and there will be a link to it on the conference website. In accordance with SIGACT policy, material that has already been published in a conference proceedings or journal, is scheduled for publication prior to July 2013, or is submitted simultaneously to another conference with published proceedings will not be considered for STOC 2013. Submissions should include all of the ideas necessary for an expert to verify the central claims but should be readable by a broad spectrum of theoretical computer scientists, not solely by experts. Authors are strongly encouraged (but not required) to make full-paper versions of their submissions available to the PC; the submission server will provide the option of uploading a full paper as well as an extended abstract. An author who cannot make a full paper available may attach a clearly marked appendix of arbitrary length to his or her extended abstract, after the bibliography. PC members are not required to read full papers or appendices; thus, authors should be sure to include all material essential for the evaluation of their submissions in their page-limited extended abstracts.

Dates:

Extended-abstract submission deadline: Friday, November 2, 2012 (4:59pm EST)
Notification: By email on Tuesday, February 5, 2013
Deadline for camera-ready copy: Wednesday, March 20, 2013
Workshops, Tutorials, and Welcome Reception: Saturday, June 1, 2013
Conference: Sunday, June 2 – Tuesday, June 4, 2013

Presentation: One author of each accepted submission is expected to present the work at STOC 2013.

Proceedings: Registered conference participants will be able to download the proceedings from a password-protected website. We intend to make them available one week before the start of the conference; authors who wish to opt out of pre-conference distribution must inform the Program Chair by email on or before Wednesday, March 20, 2013.

Tutorials, workshops, and posters: Following recent practice, STOC 2013 will include posters and a tutorial-and-workshop day. Submission instructions for posters and for tutorial and workshop proposals will be posted on the conference website on or before Friday, October 5, 2012.

Best-Paper Award: The PC may designate up to three accepted papers as STOC Best Papers. Every submission is automatically eligible for this award. Rules for this award can be found at the award site.

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 if there is a tie). For a submission to be eligible, all of its authors must be full-time students at the time of submission. To inform the PC that a submission is eligible, check the appropriate box in the submission web form. More information can be found at the award site.

Travel support: SIGACT has limited funds to support travel by students and by researchers from developing countries who do not have other means of support. Details will be posted on the conference website.