Computational Complexity

(unofficial page by Oded Goldreich)

Computational Complexity is published by Birkhauser. See the journal's webpage at the publisher's page (or at Springer Link).

Accepted papers must be formatted using the journal's style (and latex macros). You may find the relevant instructions and material at

A message from the editorial board (Feb. 2004):

We would like to encourage you to submit adequate papers to Computational Complexity (CC).

We believe that CC should be the main forum for permanent publications of papers in complexity theory. In our opinion, a high-quality specialized journal (like CC) should be a preferred option because of the following reasons:

  • Authors can have better impact on the field by publishing in CC, since their papers will be read by more complexity theorists.
  • By having a specialized journal devoted to complexity, our community proclaims and enhances its identity.
What prompts this message is that the 2002 volume of CC was only published in 2003 and consisted of two rather than the customary four issues. This was mainly due to too few good submissions, and we did not want to compromise on quality. (The delays, in turn, caused further problems with library subscriptions.)

It is up to us, the relevant research community, to change this situation by submitting enough good papers to CC to make it flourish. Certainly, the number of high-quality complexity papers every year significantly exceeds the number we can publish, so we hope this is a realistic goal. We are committed to establishing the journal as a leading journal for papers in complexity theory.

Another advantage of publishing in CC: the publisher has a very liberal policy on copyrights and electronic versions. The copyright remains with the authors, and only the commercial-distribution rights are transferred to the publisher. Authors are free to post their work on any non-commercial forum.

You are most welcome to submit papers (via email) to any member of the editorial board (see list below).

Currently, the delay between receipt of a final version of an accepted paper and its publication is quite short.

The Editorial Board: Sanjeev Arora (Assoc. Ed.), Eric Bach, Allan Borodin, Peter Borwein, Peter Buergisser (Assoc. Ed.), Harry Buhrman, Jin-Yi Cai, Steve Cook, Joachim von zur Gathen (EIC), Oded Goldreich (Assoc. Ed.), Shafi Goldwasser, Dima Grigoriev, Johan Hastad, Joos Heintz, Lane Hemaspaandra, Matthias Krause, Michael Paterson, Pavel Pudlak, Alexander Razborov, Salil Vadhan, Leslie Valiant, Avi Wigderson, and Andrew Yao.

Oded Goldreich's homepage.