Call for Papers

Computational Complexity

Twenty-first Annual IEEE Conference

July 16th to July 20th, 2006

Prague, Czech Republic

Conference Committee Program Committee

Important Dates

  • Submissions Due: Dec. 4th, 2005
  • Notification: Feb. 24th, 2006
  • Final Copies Due: April 28th, 2006

Local Arrangements

  • Václav Koubek, Charles U.
  • Daniel Kráľ, Charles U.
  • Michal Koucký, Academy of Sciences of Czech Republic
  • Antonín Kučera, Charles U.
  • Pavel Pudlák (chair), Academy of Sciences of Czech Republic
  • Milena Zeithamlová, Action M Agency
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 proof systems
  Circuits and other
    concrete computational models
  Kolmogorov complexity
  Average case complexity
Communication complexity
Complexity and logic
Cryptographic complexity
Complexity and learning
Quantum computation

A submission must be received by 23:59 EST, December 4th, 2005,  for consideration. See below for format guidelines.  Electronic submission instructions will be available from the conference's main web page no later than November 13th.  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.


The conference is sponsored by the IEEE Computer Society Technical Committee for Mathematical Foundations of Computing in cooperation with ACM SIGACT and EATCS.

More Information 

More information on the conference is available on this web site (  Information about local arrangements is available at  You may also contact the publicity chair:  John Rogers / CTI, DePaul U. / 243 S. Wabash / Chicago IL 60604, USA / E-mail: / (312) 362-8334

Electronic Submissions

We prefer electronic submissions.  The submissions web site will be available no later than November 13th. 

Submissions to other conferences

Abstract 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 2006 and will not be considered for acceptance. Authors are encouraged to submit their papers to the Electronic Colloquium on Computational Complexity.

Submission Guidelines

The conference has a firm limitation of twelve pages (in 11 point or larger fonts) on submissions.  This limit excludes the following: cover page, bibliography, and technical appendices.
Submissions deviating from these guidelines risk summary rejection.  In your abstract (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. Use appendices to substantiate your major technical results. Authors with no access to electronic submissions may contact Manindra Agarwal, the program committee chair, by e-mail to him.

Notifications of accepted papers will go out by February 24th, 2006.

Final Copies

The instructions for final copies will be communicated to authors of accepted papers.  The deadline for final copies is April 28th, 2006. 


Information on visas for travel to the Czech Republic can be found at  As early as possible, one should contact the local organizers for help and information.   

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.

Conference Abstracts

In conjunction with the conference, contributed short research abstracts will be collected and will be made available a few days before the conference. Attendance at the conference is not required to submit an abstract. For more details, check the conference web site or contact the abstracts editor:   
  Stephen Fenner
  Dept. of CSE
  U. of South Carolina
  Columbia SC 29208 USA

The Conference Site

Please see the local arrangements web site (