Data: 07/10/2021, às 16:00 horas (GMT-3, horário de Brasília).
Título: Sunflower Theorems in Monotone Circuit Complexity
Palestrante: Bruno Pasqualotto Cavalar

Resumo: Circuitos Booleanos monótonos formam uma das maiores classes de circuitos naturais para as quais existem cotas inferiores exponenciais. Tais cotas inferiores exercem um papel crucial na teoria de complexidade, como um intermediário para cotas inferiores em complexidade de comunicação, complexidade de prova e otimização. Por 20 anos, a melhor cota inferior para circuitos monótonos computando uma função Booleana explícita de $n$ bits foi $\exp{n^{1/3-o(1)}$.

Nesta palestra, motivaremos o estudo de circuitos monótonos e suas aplicações, e apresentaremos a primeira cota inferior para circuitos monótonos de ordem $\exp{n^{1/2-o(1)}$. A prova emprega o método das aproximações clássico de Razborov (1985) e cotas recentes para girassóis robustos (Alweiss, Lovett, Wu e Zhang 2020 e Rao 2020). A apresentação será auto-contida, e direções de pesquisa futuras também serão discutidas.