Call for Papers

Computational Complexity

Twenty-second Annual IEEE Conference

June 13th to June 16th, 2007

San Diego, California


Conference Committee Program Committee

Important Dates

  • Submissions Due: Dec. 3rd, 2006
  • Notification: Feb. 4th, 2007
  • Final Copies Due: Mar. 30th, 2007

Organizing Committee for FCRC

  • Daniel Menasce (General Chair), George Mason U.
  • Jim Gray (Keynote Speaker Chair), Microsoft
  • Barbara Ryder (Past FCRC General Chair), Rutgers
  • Donna Baglio (Director of SIG Services), ACM
  • Jessica Wilmers-Fried (Program Coordinator of SIG Service), ACM
  • Lance Fortnow (CCC liaison to FCRC), U. of Chicago
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 3rd, 2006,  for consideration. See below for format guidelines.  Electronic submission instructions will be available from the conference's main web page no later than November 11th.  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.  This year the conference is one of the constituent conferences of the Federated Computing Research Conference (FCRC 2007).  Please see their web site for details on FCRC and the other conferences.  

More Information 

More information on the conference is available on this web site.  Information about local arrangements will be posted when they become available.  You may also contact the publicity chair: 
  John Rogers
  CTI, DePaul U.
  243 S. Wabash
  Chicago IL 60604 USA


Electronic Submissions

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

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 (including STOC 2007) 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 imposed a firm limitation of twenty pages (in 11 point or larger font) on submissions. This limit includes the bibliography and any 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.  Authors with no access to electronic submissions may contact Peter Bro Miltersen, the program committee chair, by e-mail.

Notifications of accepted papers will go out by February 4th, 2007.

Final Copies

The instructions for final copies will be communicated to authors of accepted papers.  The deadline for final copies is March 30th, 2007. 


Visa processing by US consulates can take several months. If you are a citizen of one of the countries where the US requires a visa for entry we recommend you start the application process as soon as you think you will be attending the conference. Please contact the conference organizers if you need a letter to help you attain your visa.

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.

The Federated Computing Research Conference

This year the conference will be a part of the Federated Computing
Research Conference (FCRC 2007). As stated on the web site: "FCRC assembles a spectrum of affiliated research conferences and workshops into a week long coordinated meeting held at a common time in a common place. This model retains the advantages of the smaller conferences and, at the same time, facilitates communication among researchers in different fields in computer science and engineering. Mornings of FCRC week will begin with joint plenary talks on topics of broad appeal to the computing research community." (


Page last updated on August 16th, 2006.