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, 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)

  • 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
Editor-in-chief
  • Peter Bürgisser
Publishing model
Hybrid. Open Choice – What is this?
Impact
Impact factor: 0.822 (2018)
Five year impact factor: 1.000 (2018)
Speed
Acceptance to publication: 22 days
Usage
Downloads: 6,847 (2018)

Articles

Journal updates

View all updates

About this journal

Electronic ISSN
1420-8954
Print ISSN
1016-3328
Abstracted and indexed in
  1. ACM Digital Library
  2. Current Contents/Engineering, Computing and Technology
  3. DBLP
  4. EBSCO Applied Science & Technology Source
  5. EBSCO Computer Science Index
  6. EBSCO Computers & Applied Sciences Complete
  7. EBSCO Discovery Service
  8. EBSCO Engineering Source
  9. EBSCO STM Source
  10. Gale
  11. Gale Academic OneFile
  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. zbMATH
Copyright information

Rights and permissions

Springer Nature policies

© Springer Nature Switzerland AG