Call for Papers

The 42nd ACM Symposium on Theory of Computing (STOC 2010), sponsored by the ACM Special Interest Group on Algorithms and Computation Theory (SIGACT), will be held in Cambridge, Massachusetts, from Sunday June 6 to Tuesday June 8, 2010. 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, cryptography, privacy, computational geometry, algorithmic graph theory and combinatorics, optimization, randomness in computing, approximation algorithms, parallel and distributed computation, machine learning, applications of logic, algorithmic algebra and coding theory, computational biology, computational game theory, quantum computing, and theoretical aspects of areas such as robotics, databases, information retrieval, and networks. Papers that broaden the reach of theory, or raise important problems that can benefit from theoretical investigation and analysis, are encouraged.

Submission format: Authors should submit an extended abstract (not a full paper). The extended abstract should start with a title page consisting of the title of the paper; each author’s name, affiliation, and email address; and a brief summary of the results to be presented (one or two paragraphs in length). This should be followed by a technical exposition of the main ideas and techniques used to achieve the results, including motivation and a clear comparison with related work.

The extended abstract should be addressed insofar as possible to a broad spectrum of CS Theory researchers. Authors should clearly convey to such a reader the main new ideas in the paper. One suggested, but not required, way of achieving this is to include a short section containing either the equivalent of a brief oral presentation of the work, or a discussion of the conceptual contributions of the paper, or a sketch of the key ideas in the proof of the simplest non-trivial statement of the main result.

Authors should substantiate the principal claims in the paper. If necessary, some material may be placed in a clearly marked appendix that will be read at the discretion of the program committee. There are no format requirements regarding such an appendix. (Authors are encouraged to simply attach a copy of the full paper, if ready.)

The body of the extended abstract (excluding title page and bibliography) should not exceed 10 single-spaced pages on letter-size (8 1/2 x 11 inch) paper, and should be in single-column format, using at least 1 inch margins and at least 11-point font.

Submissions deviating significantly from these guidelines risk rejection without consideration of their merits.

Extended Abstract Submission: Authors are required to submit their extended abstracts electronically, in PDF (without security restrictions on copying or printing). The submission server is accessible through the following link: https://secure.iacr.org/websubrev/stoc2010/submit/. Submissions will be judged solely on the basis of the extended abstract submitted by the deadline; postdeadline revisions will not be allowed.

Simultaneous Submissions: The conference will follow SIGACT’s policy on simultaneous submissions and prior publication. Abstract material which has been previously published in another conference proceedings or journal, or which is scheduled for publication prior to July 2010, will not be considered for acceptance at STOC 2010. SIGACT policy does not allow simultaneous submissions of the same (or essentially the same) abstract material to another conference with published proceedings.

Dates:

Extended Abstract Submission: Thursday November 5, 2009 (3:59pm PST).
Notification will be by email on or before February 9, 2010.
Deadline for accepted papers: A camera-ready copy of each accepted paper is required by March 30, 2010. Tutorials and Welcome Reception: Saturday June 5, 2010.
Conference: Sunday June 6 – Tuesday June 8, 2010.

Presentation of Accepted Papers: One author of each accepted paper will be expected to present the work at the conference.

Best Paper Award: The program committee may designate up to three papers accepted to the conference as STOC Best Papers. Every submission is automatically eligible for this award. Rules for the award can be found at http://sigact.acm.org/prizes/bestpaper.

Danny Lewin Best Student Paper Award: A prize of $500 will be given to the author(s) of the best studentauthored 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 http://sigact.acm.org/prizes/student.

Program Committee:

Local Arrangements Committee: Christian Borgs, Jennifer Chayes, Henry Cohn, Erik Demaine, Yael Tauman Kalai and Paul Oka.

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 30.

SIGACT provides travel awards to needy students, and researchers from developing countries. The 2009 award process is described at http://www.umiacs.umd.edu/conferences/stoc2009/travel-support.shtml The 2010 process will be similar.