Disciplina Curricular
Tópicos Avançados de Complexidade Computacional TACC
Doutoramento Bolonha em Matemática - 4_DMat 2022/23
Contextos
Grupo: 4_DMat 2022/23 > 3º Ciclo > Parte Escolar > Opcionais > 93_Doutoramento em Matemática
Período:
Peso
6.0 (para cálculo da média)
Objectivos
O curso oferecerá uma introdução intensa ao campo da Complexidade Computacional. O curso será organizado historicamente, abrangendo desde o início da área, até o início dos anos 2000.
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
Métodos de ensino e avaliação
As aulas cobrem a teoria. O estudo em casa cobre a componente prática. Todas as semanas haverá tarefa de leitura e TPC. No final do semestre haverá apresentações dos alunos.