CCC'17: Call for Papers

Submission Deadline: Wednesday, February 15, 2017, 5:00pm EST

Scope

The conference seeks original research papers in all areas of computational complexity theory, studying the absolute and relative power of computational models under resource constraints. We also encourage contributions from other areas of computer science and mathematics motivated by topics in complexity theory. Possible topics include but are not limited to:

Complexity classes Circuit complexity Algebraic complexity Proof complexity Interactive and probabilistic proof systems Complexity in other concrete computational models Reducibility and completeness Logic and descriptive complexity

Average case complexity Communication complexity Complexity of optimization, including inapproximability Complexity and cryptography Complexity and learning Complexity and coding theory Complexity and sublinear computation Pseudorandomness and derandomization Quantum computation

Submission

Deadlines: Papers must be submitted electronically via the submission server, and received by February 15, 2017, 5:00pm EST. (This is one week after the STOC 2017 notification date.) Notification of acceptance will be sent by April 26, 2017 April 19, 2017, and final camera-ready copies of accepted papers will be due in the second week of May 2017.

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 10 pages a clear presentation of the merits of the paper, including discussion of its importance, prior work, and an outline of key technical ideas and methods used to achieve the main claims. There is no bound on the total length of a submission, but material other than the abstract, references, and the first 10 pages is considered as supplementary.

Submissions should include proofs of all central claims.

The submission should be in single-column format, use at least 11-point font, and have standard margins and spacing between lines. Submissions deviating from these guidelines risk rejection without consideration of their merits. Instructions for formatting camera-ready versions will be communicated to the authors of accepted papers.

Additional remarks: In addition to the submission, authors may optionally send a short email to the PC chair ccc2017chair@gmail.com containing any additional remarks for the PC, such as the relationship of with independent/concurrent work, differences from prior versions, conflict of interest statements, or clarifications concerning prior reviews of the work. Authors can also use this email to state that they are eligible for the Best student paper award.

Simultaneous submission policy: Material which has been previously published in a journal or another conference proceedings, or which is scheduled for publication prior to July 2017, will not be considered for acceptance.  Simultaneous submission of the same or essentially the same material to another conference with published proceedings is not allowed.

Confidentiality: All submissions will be treated as confidential, and will only be disclosed to the committee and their chosen sub-referees.

Publication

Online posting: Authors are encouraged to post full versions of their submissions in a freely accessible on-line repository such as the Electronic Colloquium on Computational Complexity or the arXiv. It is hoped that authors of accepted papers will make full versions of their papers publicly available by the camera-ready deadline.

Proceedings: Conference proceedings will be published under a Creative Commons BY license in the Leibniz International Proceedings in Informatics (LIPIcs) series. Publication in the conference proceedings does not preclude subsequent journal publication.

Presentation: Authors of accepted papers are expected to present their work at the conference. The program committee will determine time allocations for presentations (between 15 and 45 minutes).

Awards

Best student paper award: This award will be given to the best paper written solely by one or more students as judged by the program committee. A paper is eligible if all authors are full-time students at the time of submission deadline. Authors should indicate their eligibility with an email to ccc2017chair@gmail.com. The program committee may decline to make the award or may split it among several papers. Funding for the best student paper award is provided by EATCS.

Best paper award: This award will be given to the best paper submitted to the conference as judged by the program committee. The program committee may decline to make the award or may split it among two or more papers. Authors of papers that receive this award are automatically invited to publish a full version of the paper in the Journal of the ACM.

Special journal issue: The program committee will invite full versions of a select number of conference submissions to a special issue of the journal Theory of Computing.

Conference Information

Dates and location: The conference will be held from Thursday July 6 to Sunday July 9, 2017 in Riga, Latvia. Some additional tutorial programming may be scheduled for the afternoon of Wednesday July 5, and the conference will end in the early afternoon on Sunday. (As a note, ICALP 2017 will take place directly afterward, July 10-14 in Warsaw, Poland.)

Travel allowances: In order to defray the costs of attending the conference, travel allowances will be offered to students and needy researchers. There are two sources: one from NSF for students from US institutions, and one from the local organizers. The details of the application procedure will be announced on the local arrangements web site in due time.

Visas: A visa for Latvia may be needed for attending the conference, e.g., for citizens of China, India, and Russia. See the visa website of the Latvian government for the exact rules for short-term stay visas. If a visa is needed, please get in touch with your local Latvian consulate as soon as possible. Feel free to contact the local arrangements team if you need a letter to obtain your visa.

Program Committee

• Manindra Agrawal, IIT Kanpur
• Eli Ben-Sasson, Technion
• Amit Chakrabarti, Dartmouth College
• Kai-Min Chung, Academia Sinica
• Dmitry Gavinsky, Czech Academy of Sciences
• Joshua Grochow, University of Colorado, Boulder and the Santa Fe Institute
• Michal Koucký, Charles University
• Shachar Lovett, UC San Diego
• Ryan O'Donnell (chair), Carnegie Mellon University
• Dana Ron, Tel Aviv University
• Benjamin Rossman, University of Toronto

Local Arrangements Committee

• Andris Ambainis (chair), University of Latvia
• Dace Mileika, University of Latvia
• Alexander Rivosh, University of Latvia
• Raqueline Santos, University of Latvia
• Juris Smotrovs, University of Latvia

Board of Trustees

• Eric Allender (Treasurer), Rutgers University
• Boaz Barak, Harvard University
• Sevag Gharibian (Secretary), Virginia Commonwealth University
• Venkatesan Guruswami, Carnegie Mellon University
• Dieter van Melkebeek (President), University of Wisconsin-Madison
• Ryan O'Donnell, Carnegie Mellon University
• Rocco Servedio, Columbia University
• Jacobo Toran, University of Ulm
• Osamu Watanabe, Tokyo Institute of Technology

Questions?

Please contact Sevag Gharibian.