Skip to main content

computational complexity

1998 - 2024
Jahrgänge
91
Ausgaben
Chevron right icon
Ausgabe 2/2024
Aktuelle Ausgabe

Über diese Zeitschrift

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.30 (2015)

Metadaten
Titel
computational complexity
Abdeckung
Jahrgang 7/1998 - Jahrgang 33/2024
Verlag
Springer International Publishing
Elektronische ISSN
1420-8954
Print ISSN
1016-3328
Zeitschriften-ID
37
DOI
https://doi.org/10.1007/37.1420-8954