Programa

Complexidade Computacional

Mestrado Bolonha em Engenharia Informática

Mestrado Bolonha em Ciência de Dados

Mestrado Bolonha em Segurança Informática

Mestrado Bolonha em Matemática

Mestrado Bolonha em Bioinformática e Biologia Computacional

Programa

Part 1 - Complexity Classes and Diagonalization * The invention of the computer: Turing's machines and the halting problem. * Complexity measures and Random-Access Machines. * Hierarchy theorems. * Godel's lost letter, reductions, the Cook-Levin theorem, and the P versus NP problem. * Space complexity: L vs NL vs P vs PSPACE. * The Relativization barrier Part 2 - The combinatorial approach. * Combinatorial models: Boolean Circuits and Formulas, trivial lower-bounds, depth-reduction * Randomized computation: ZPP, RP, BPP, the quest for derandomization, Hardness versus Randomness. * Algorithms and lower-bounds for constant-depth circuits. * The current frontier in circuit lower-bounds: Constant-depth circuits with modular gates * Communication complexity and the Karchmer-Wigderson theorem * Some lower-bounds in Communication Complexity * The Natural-Proofs Barrier Part 3 - Other topics (student presentations; if time is lacking, some of the above will be moved to student presentations, also.) * Interactive proofs * Probabilistically-checkable proofs * Hardness of approximation * Cryptographic primitives and security * Discrepancy * Lifting theorems * Proof Complexity