Aims and scope

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