CCC 2009: Call for Papers
Purpose and Scope
The conference seeks original research papers in all areas of computational complexity theory. We also encourage results from other areas of computer science and mathematics motivated by topics in complexity theory.
The following list of possible topics is not exhaustive:
- Complexity classes
- Algebraic complexity
- Proof complexity
- Interactive and probabilistic proof systems
- Circuits complexity
- Kolmogorov complexity
- Reducibility and completeness
- Communication complexity
- Cryptographic complexity
- Complexity and learning
- Complexity and logic
- Quantum computation
- Average case complexity
- Pseudorandomness and derandomization
- Complexity in other concrete computational models
Location and Dates
The 2009 conference will be held from July 15th to July 18th, 2009, in Paris's historic Latin Quarter. See the navigation list for a preliminary local arrangements site and to find travel information.
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).
We prefer electronic submissions. A submission must be received by February 13th, 2009, 23:59 EST, for consideration. The submission server is now open. Notification of acceptance will be sent by April 7th, 2009, and final copies will be due by May 6th, 2009.
A submission should be in single-column format, use at least 11 point font, and have standard margins and spacing between lines. Submissions may be of arbitrary length, but we encourage submission of a total of at most 25 pages and require that the first 10 pages of the submission allow a sound evaluation of the submission's merits. Later text will be considered as supplementary material and will be read at the committee's discretion only. Thus, within the first 10 pages the submission should (i) explain what the paper's major contributions are, (ii) convey why these contributions are interesting, and (iii) tell how these contributions relate to prior work.
Material which has been previously published in another conference proceedings or journal or which is simultaneously submitted to another conference with published proceedings may not be submitted to Computational Complexity 2009 and will not be considered for acceptance. Authors are encouraged to submit their papers to the Electronic Colloquium on Computational Complexity.
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.
- Harry Buhrman, CWI and University of Amsterdam
- Anna Gál, University of Texas, Austin
- Oded Goldreich, Weizmann Institute
- Johan Håstad (chair), KTH, Stockholm
- Matthias Krause, University of Mannheim
- Ryan O'Donnell, CMU
- Alexander Razborov, University of Chicago
- Oded Regev, Tel Aviv University
- Chris Umans, Caltech
- Sergey Yekhanin, Microsoft, Mountain View
A mini-poster version of the CFP is available as a PDF.
If you have any questions, please e-mail John Rogers, the publicity chair. You may also send mail to:
CDM, DePaul University
243 S. Wabash
Chicago IL 60604, USA