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:

  • cryptography
  • 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, 2 issues per volume
approx. 500 pages per volume
Format: 15.5 x 23.5 cm
ISSN 1016-3328 (print)
ISSN 1420-8954 (electronic)

AMS Mathematical Citation Quotient (MCQ): 0.75 (2018)

  • A resource for outstanding research in computational complexity
  • Covers models of computation, complexity bounds, complexity classes and more
  • Explores the structure of complexity classes, algebraic complexity, the role of randomness, and issues in cryptography, robotics, logic and distributed computing

Journal information

  • Peter Bürgisser
Publishing model
Hybrid (Transformative Journal). Learn about publishing Open Access with us

Journal metrics

0.850 (2019)
Impact factor
0.737 (2019)
Five year impact factor
7,904 (2020)

Latest articles

This journal has 30 open access articles

Journal updates

View all updates

About this journal

Electronic ISSN
Print ISSN
Abstracted and indexed in
  1. ACM Digital Library
  2. CNKI
  3. Current Contents/Engineering, Computing and Technology
  4. DBLP
  5. Dimensions
  6. EBSCO Applied Science & Technology Source
  7. EBSCO Computer Science Index
  8. EBSCO Computers & Applied Sciences Complete
  9. EBSCO Discovery Service
  10. EBSCO Engineering Source
  11. EBSCO STM Source
  12. Google Scholar
  13. INSPEC
  14. Institute of Scientific and Technical Information of China
  15. Japanese Science and Technology Agency (JST)
  16. Journal Citation Reports/Science Edition
  17. Mathematical Reviews
  18. Naver
  19. OCLC WorldCat Discovery Service
  20. ProQuest Advanced Technologies & Aerospace Database
  21. ProQuest Central
  22. ProQuest Engineering
  23. ProQuest Materials Science and Engineering Database
  24. ProQuest SciTech Premium Collection
  25. ProQuest Technology Collection
  26. ProQuest-ExLibris Primo
  27. ProQuest-ExLibris Summon
  28. SCImago
  29. SCOPUS
  30. Science Citation Index Expanded (SciSearch)
  31. TD Net Discovery Service
  32. UGC-CARE List (India)
  33. zbMATH
Copyright information

Rights and permissions

Springer policies

© Springer Nature Switzerland AG