Programa

Tópicos Avançados de Complexidade Computacional

Doutoramento Bolonha em Matemática

Programa

Parte 1 - Classes de Complexidade e Diagonalização * A invenção do computador: as máquinas de Turing e o problema da parada. * Medidas de complexidade e máquinas de acesso aleatório. * Teoremas de hierarquia. * A carta de Gödel, reduções, teorema de Cook-Levin e problema P versus NP. * Complexidade espacial: L vs NL vs P vs PSPACE. * A barreira da relativização Parte 2 - A abordagem combinatória. * Modelos combinatórios: circuitos e fórmulas booleanas, limites inferiores triviais, redução de profundidade * Computação randomizada: ZPP, RP, BPP, a busca pela desrandomização, Dureza versus Aleatoriedade. * Algoritmos e limites inferiores para circuitos de profundidade constante. * A fronteira atual nos limites inferiores do circuito: circuitos de profundidade constante com portas modulares * Complexidade da comunicação e teorema de Karchmer-Wigderson * Alguns lower-bounds na complexidade da comunicação * The natural-proofs barrier Parte 3 - Outros tópicos (apresentações dos alunos; se faltar tempo, alguns dos itens acima também serão transferidos para as apresentações dos alunos). * Interactive proofs * Probabilistically-checkable proofs * Hardness of approximation * Cryptographic primitives and security * Discrepancy * Lifting theorems * Proof Complexity * Fourier analysis of Boolean functions * Convex optimization * Lattice problems * Geometeric Complexity Theory * Hardness amplification * Quantum computing