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
- Editor-in-Chief
-
- 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
- 6,883 (2019)
- Downloads
Latest issue
Latest articles
Journal updates
-
Computational-Complexity Website
http://www.computational-complexity.org
About this journal
- Electronic ISSN
- 1420-8954
- Print ISSN
- 1016-3328
- Abstracted and indexed in
-
- ACM Digital Library
- CNKI
- Current Contents/Engineering, Computing and Technology
- DBLP
- Dimensions
- EBSCO Applied Science & Technology Source
- EBSCO Computer Science Index
- EBSCO Computers & Applied Sciences Complete
- EBSCO Discovery Service
- EBSCO Engineering Source
- EBSCO STM Source
- Google Scholar
- INSPEC
- Institute of Scientific and Technical Information of China
- Japanese Science and Technology Agency (JST)
- Journal Citation Reports/Science Edition
- Mathematical Reviews
- Naver
- OCLC WorldCat Discovery Service
- ProQuest Advanced Technologies & Aerospace Database
- ProQuest Central
- ProQuest Engineering
- ProQuest Materials Science and Engineering Database
- ProQuest SciTech Premium Collection
- ProQuest Technology Collection
- ProQuest-ExLibris Primo
- ProQuest-ExLibris Summon
- SCImago
- SCOPUS
- Science Citation Index Expanded (SciSearch)
- TD Net Discovery Service
- UGC-CARE List (India)
- zbMATH
- Copyright information