The 48th ACM Symposium on Theory of Computing (STOC 2016), sponsored by the ACM Special Interest Group on Algorithms and Computation Theory (SIGACT), will be held in Cambridge, MA, from Saturday, June 18 to Tuesday, June 21, 2016. Papers presenting new and original research on the theory of computation are sought. Topics of interest include, but are not limited to: algorithms and data structures, computational complexity, randomness in computing, algorithmic graph theory and combinatorics, approximation algorithms, cryptography, computational learning theory, economics and computation, parallel and distributed algorithms, quantum computing, algorithmic coding theory, computational geometry, computational applications of logic, optimization, algebraic algorithms, and theoretical aspects of areas such as networks, privacy, computational biology, and databases. Papers that broaden the reach of the theory of computing, or raise important problems that can benefit from theoretical investigation and analysis, are encouraged.

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. This should be followed by an extended abstract of up to 10 pages, which consists of a scholarly exposition of the paper's main ideas, results, and techniques, 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 also substantiate the main mathematical claims of the paper with proofs, some of which may be placed in a clearly marked appendix that will be read at the discretion of the program committee. If desired, the authors can simply attach a copy of the full paper as the appendix (for instructions on how to do this, see this ). The body of the extended abstract (excluding title page, bibliography, appendix, and figures) 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, 11-point font, and ample spacing all around. Submissions deviating significantly from these guidelines risk rejection without consideration of their merits.

Submission Instructions: Authors are required to submit their extended abstracts electronically, in PDF (without security restrictions on copying or printing). The submission server will be available by early October through the following link: https://secure.iacr.org/websubrev/stoc2016/submit/

Authors are encouraged to also make full versions of their submissions freely accessible in an on-line 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 by the camera-ready deadline.

Prior and Simultaneous Submissions: The conference will follow SIGACT's policy on prior publication and simultaneous submissions. Abstract material which has been previously published in another conference proceedings or journal, or which is scheduled for publication prior to July 2016, will not be considered for acceptance at STOC 2016. 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) abstract 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:

Extended Abstract Submission: Monday November 2, 2015 (23:59pm EST).
Notification: by email on or before February 5, 2016.
Deadline for accepted papers: A camera-ready copy of each accepted paper is required by March 19, 2016.
Workshops and tutorials: Saturday June 18, 2016, will be held jointly with the 32nd International Symposium on Computational Geometry (SOCG 2016).
Welcome Reception: Saturday June 18, 2016.
Conference: Sunday June 19 to Tuesday June 21, 2016.

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://www.sigact.org/Prizes/BestPaper.

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 http://www.sigact.org/Prizes/Student.

Program Chair: Yishay Mansour (Microsoft Research and Tel Aviv University)

Program Committee:
Alexandr Andoni, Columbia University
Sanjeev Arora, Princeton University
Allison Bishop, Columbia University
Avrim Blum, Carnegie Mellon University
Keren Censor-Hillel, Technion
Timothy Chan, University of Waterloo
Chandra Chekuri, University of Illinois, Urbana-Champaign
Jing Chen, Stony Brook University
Zeev Dvir, Princeton University
Fabrizio Grandoni, IDSIA
Parikshit Gopalan, Microsoft Research
Kasper Green Larsen, Aarhus University
Huijia (Rachel) Lin, UC Santa Barbara
Konstantin Makarychev, Microsoft Research
Yishay Mansour (chair), Microsoft Research and Tel Aviv University
Jakob Nordstrom, KTH Royal Institute of Technology
Debmalya Panigrahi, Duke University
Prasad Raghavendra, UC Berkeley
Sofya Raskhodnikova, Pennsylvania State University
R Ravi, Carnegie Mellon University
Mario Szegedy, Rutgers University
Éva Tardos, Cornell University
Salil Vadhan, Harvard University and National Chiao Tung University
Avi Wigderson, Institute for Advanced Study
Ronald de Wolf, CWI and University of Amsterdam

General Chair: Daniel Wichs, Northeastern University

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

SIGACT provides travel awards to students without available support and researchers from developing countries. More information on the award process will be posted shortly.