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 computationfor 'general' and 'structured' computation for deterministic, probabilistic, and nondeterministic computationworst case and average caseSpecific areas of concentration include:
Structure of complexity classes (reductions, relativization questions, degrees, derandomization)Algebraic complexity Cryptography, interactive proofs, pseudorandom generation |
