Monday, August 29, 2011

Conference on Computational Complexity 2012: Call for Papers

CONFERENCE ON COMPUTATIONAL COMPLEXITY: CALL FOR PAPERS
Submission Deadline: Thursday, December 8, 2011, 19:59 EST
      
PURPOSE AND 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 results from other areas of computer science and mathematics motivated by topics in complexity theory. The following list of sample topics is not exhaustive: 

Complexity classes, Algebraic complexity, Proof complexity, Interactive and probabilistic proof systems, Circuit complexity, Kolmogorov complexity, Logic and descriptive complexity, Average case complexity, Reducibility and completeness, Communication complexity, Complexity in other concrete computational models, Cryptographic complexity, Complexity of optimization and inapproximability, Complexity and learning, Complexity and coding theory, Pseudorandomness and derandomization, Complexity and sub-linear computation, Quantum computation
      
CONFERENCE LOCATION AND DATES:

The 2012 conference will be held from June 26th to June 29th, 2012, in Porto, Portugal, and is organized in association with the 2012 Alan Turing Year. In order to defray the costs of attending an overseas conference, some travel awards are available for students from US institutions. More information about travel and local arrangements will be made available on the conference webpage in due time. 
 
SPONSORS:
The conference is sponsored by the IEEE Computer Society Technical Committee for Mathematical Foundations of Computing in cooperation with the ACM Special Interest Group on Algorithms and Computation Theory (SIGACT) and the European Association of Theoretical Computer Science (EATCS). The National Science Foundation (NSF) provides student travel support through award CCF-1143914.
SUBMISSIONS:

Papers must be submitted electronically, and received by December 8th, 2011, 19:59 EST, for consideration. The submission server will be active a few weeks before the submission deadline. Notification of acceptance will be sent by February 17th, 2012, and final camera-ready copies of accepted papers will be due around mid-March 2012.

Submission format: 

A submission should consist of a title page (containing the title, author names and affiliations, and an abstract of 1-2 paragraphs summarizing the paper's contributions), a body of no more than 10 pages, a bibliography, and possible appendices. The paper 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 summary rejection without consideration of their merits.

The body of the paper should (i) explain what the major contributions are, (ii) convey why they are interesting, (iii) discuss how they relate to prior work, and (iv) present the main ideas behind them. Authors are expected to include all ideas necessary for an expert to fully verify the central claims in the paper, and may use appendices to substantiate technical claims as needed. The appendices will be read at the discretion of the Program Committee. (Authors may, if they prefer, simply attach a copy of the full paper as the appendix.)

All submissions will be treated as confidential, and will only be disclosed to the committee and their chosen sub-referees. The instructions for the format of final copies will be communicated to the authors of accepted papers.

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, 2012, 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.

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, with proofs, available by the camera-ready deadline. (This should be done in a manner consistent with the IEEE Copyright Policy.)

Presenting the work: 

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). Conference proceedings will be published by the IEEE Computer Society. Publication in the conference proceedings does not preclude subsequent journal publication.

Ronald V. Book Prize for Best Student Paper: 

This award will be given to the best paper written solely by one or more students. An abstract is eligible if all authors are full-time students at the time of submission. This should be indicated in the submission registration message or cover letter. The program committee may decline to make the award or may split it among several papers.

Best Paper Award: 

This award will be given to the best paper submitted to the conference. This will be awarded by the program committee. The program committee may decline to make the award or may split it among several papers.

PROGRAM COMMITTEE:

Eric Allender, Rutgers University
Boaz Barak, Microsoft Research New England
Irit Dinur, Weizmann Institute
Nicola Galesi, University of Rome "La Sapienza"
Venkatesan Guruswami (chair), Carnegie Mellon University
Neeraj Kayal, Microsoft Research India
Julia Kempe, Univ. of Paris 7 and Tel Aviv University
Hartmut Klauck, Nanyang Technological University
Rahul Santhanam, University of Edinburgh
Rocco Servedio, Columbia University
Amir Yehudayoff, Technion

Local Arrangement Chair: Luis Antunes (Porto University)

Publicity Chair: Richard Beigel (Temple University)

Conference website: computationalcomplexity.org