Zeitschrift, Englisch
Erscheinungsweise: halbjährlich
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
