Disciplina Curricular

Complexidade Computacional CC

Mestrado Bolonha em Matemática - 2_MMat 2022/23

Contextos

Peso

6.0 (para cálculo da média)

Objectivos

The course will offer an intense introduction to the field of Computational Complexity. The course will be organized historically, covering the time since the very beginning of the field, up to the early 2000s.

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

Métodos de ensino e avaliação

Classes cover the theory. Every week there will be a reading assignment and homework. At the end of the semester there will be student presentations.

Disciplinas Execução

2023/2024 - 1 Semestre