Logo - springer
Slogan - springer

Birkhäuser - Computer sciences and Informatics | computational complexity (Editorial Board)

computational complexity
Birkhäuser Basel

computational complexity

Editor-in-Chief: Peter Bürgisser

ISSN: 1016-3328 (print version)
ISSN: 1420-8954 (electronic version)

Journal no. 37

Birkhäuser Basel

Peter Bürgisser
Berlin, Germany

Associate editors

Sanjeev Arora
Princeton NJ, USA

Oded Goldreich
Rehovot, Israel

Dieter van Melkebeek
Madison WI, USA

Editorial board

Markus Bläser
Saarbrücken, Germany

Harry Buhrman
Amsterdam, Netherlands

Jin-Yi Cai
Madison WI, USA

Stephen A. Cook
Toronto ON, Canada

Irit Dinur
Rehovot, Israel

Joachim von zur Gathen
Bonn, Germany

Shafi Goldwasser
Cambridge MA, USA

Dima Grigoriev
Lille, France

Johan Håstad
Stockholm, Sweden

Joos Heintz
Buenos Aires, Argentina

Lane A. Hemaspaandra
Rochester NY, USA

Yuval Ishai
Haifa, Israel

Valentine Kabanets
Vancouver BC, Canada

Pascal Koiran
Lyon, France

François Le Gall
Kyoto, Japan

Mike Paterson
Coventry, UK

Pavel Pudlak
Praha, Czech Republic

Alexander Razborov
Chicago IL, USA

Amir Shpilka
Haifa, Israel

Chris Umans
Pasadena CA, USA

Salil Vadhan
Cambridge MA, USA

Leslie G. Valiant
Cambridge MA, USA

Virginia Vassilevska Williams
Cambridge MA, USA

Avi Wigderson
Princeton NJ, USA

Andrew C.C. Yao
Beijing, China

Read this Journal on Springerlink

For authors and editors

  • Journal Citation Reports®
    2017 Impact Factor
  • 0.487
  • Aims and Scope

    Aims and Scope


    computational complexity presents outstanding research in computational complexity. Its subject is at the interface between mathematics and theoretical computer science, with a clear mathematical profile and strictly mathematical format.

    The central topics are:

    Models of computation, complexity bounds (with particular emphasis on lower bounds), complexity classes, trade-off results

    • for sequential and parallel computation
    • for "general" (Boolean) and "structured" computation (e.g. decision trees, arithmetic circuits)
    • for deterministic, probabilistic, and nondeterministic computation
    • worst case and average case

    Specific areas of concentration include:

    • Structure of complexity classes (reductions, relativization questions, degrees, derandomization)
    • Algebraic complexity (bilinear complexity, computations for polynomials, groups, algebras, and representations)
    • Interactive proofs, pseudorandom generation, and randomness extraction

    Complexity issues in:

    • crytography
    • learning theory
    • number theory
    • logic (complexity of logical theories, cost of decision procedures)
    • combinatorial optimization and approximate Solutions
    • distributed computing
    • property testing

    Bibliographic Data
    comput. complex.
    First published in 1991
    1 volume per year, 4 issues per volume
    approx. 800 pages per volume
    Format: 15.5 x 23.5 cm
    ISSN 1016-3328 (print)
    ISSN 1420-8954 (electronic)

    AMS Mathematical Citation Quotient (MCQ): 0.45 (2017)

  • Submit Online
  • Open Choice - Your Way to Open Access
  • Additional Copyright Information

    Additional Copyright Information


  • Instructions for Authors

    Instructions for Authors - computational complexity


  • Computational-Complexity.org
  • Author Academy: Training for Authors
  • Copyright Information

    Copyright Information


    Copyright Information

    For Authors

    Submission of a manuscript implies: that the work described has not been published before (except in form of an abstract or as part of a published lecture, review or thesis); that it is not under consideration for publication elsewhere; that its publication has been approved by all co-authors, if any, as well as – tacitly or explicitly – by the responsible authorities at the institution where the work was carried out.

    Author warrants (i) that he/she is the sole owner or has been authorized by any additional copyright owner to assign the right, (ii) that the article does not infringe any third party rights and no license from or payments to a third party is required to publish the article and (iii) that the article has not been previously published or licensed. The author signs for and accepts responsibility for releasing this material on behalf of any and all co-authors. Transfer of copyright to Springer (respective to owner if other than Springer) becomes effective if and when a Copyright Transfer Statement is signed or transferred electronically by the corresponding author. After submission of the Copyright Transfer Statement signed by the corresponding author, changes of authorship or in the order of the authors listed will not be accepted by Springer.

    The copyright to this article, including any graphic elements therein (e.g. illustrations, charts, moving images), is assigned for good and valuable consideration to Springer effective if and when the article is accepted for publication and to the extent assignable if assignability is restricted for by applicable law or regulations (e.g. for U.S. government or crown employees).

    The copyright assignment includes without limitation the exclusive, assignable and sublicensable right, unlimited in time and territory, to reproduce, publish, distribute, transmit, make available and store the article, including abstracts thereof, in all forms of media of expression now known or developed in the future, including pre- and reprints, translations, photographic reproductions and microform. Springer may use the article in whole or in part in electronic form, such as use in databases or data networks for display, print or download to stationary or portable devices. This includes interactive and multimedia use and the right to alter the article to the extent necessary for such use.

    Authors may self-archive the Author's accepted manuscript of their articles on their own websites. Authors may also deposit this version of the article in any repository, provided it is only made publicly available 12 months after official publication or later. He/she may not use the publisher's version (the final article), which is posted on SpringerLink and other Springer websites, for the purpose of self-archiving or deposit. Furthermore, the Author may only post his/her version provided acknowledgement is given to the original source of publication and a link is inserted to the published article on Springer's website. The link must be accompanied by the following text: "The final publication is available at link.springer.com".

    Prior versions of the article published on non-commercial pre-print servers like arXiv.org can remain on these servers and/or can be updated with Author's accepted version. The final published version (in pdf or html/xml format) cannot be used for this purpose. Acknowledgement needs to be given to the final publication and a link must be inserted to the published article on Springer's website, accompanied by the text "The final publication is available at link.springer.com". Author retains the right to use his/her article for his/her further scientific career by including the final published journal article in other publications such as dissertations and postdoctoral qualifications provided acknowledgement is given to the original source of publication.

    Author is requested to use the appropriate DOI for the article. Articles disseminated via link.springer.com are indexed, abstracted and referenced by many abstracting and information services, bibliographic networks, subscription agencies, library networks, and consortia.

    For Readers

    While the advice and information in this journal is believed to be true and accurate at the date of its publication, neither the authors, the editors, nor the publisher can accept any legal responsibility for any errors or omissions that may have been made. The publisher makes no warranty, express or implied, with respect to the material contained herein.

    All articles published in this journal are protected by copyright, which covers the exclusive rights to reproduce and distribute the article (e.g., as offprints), as well as all translation rights. No material published in this journal may be reproduced photographically or stored on microfilm, in electronic data bases, video disks, etc., without first obtaining written permission from the publisher (respective the copyright owner if other than Springer). The use of general descriptive names, trade names, trademarks, etc., in this publication, even if not specifically identified, does not imply that these names are not protected by the relevant laws and regulations.

    Springer has partnered with Copyright Clearance Center's RightsLink service to offer a variety of options for reusing Springer content. For permission to reuse our content please locate the material that you wish to use on link.springer.com or on springerimages.com and click on the permissions link or go to copyright.com, then enter the title of the publication that you wish to use. For assistance in placing a permission request, Copyright Clearance Center can be connected directly via phone: +1-855-239-3415, fax: +1-978-646-8600, or e-mail: info@copyright.com.

    © Springer Nature Switzerland

Alerts for this journal


Get the table of contents of every new issue published in computational complexity.