Teoremas de girassol em complexidade computacional

Autor(es)

Bruno Pasqualotto Cavalar

• Tipo de documento: Dissertação de Mestrado
• Imprenta: São Paulo.
• Instituição: Universidade de São Paulo (USP). Instituto de Matemática e Estatística (IME/SBI)
• Data de defesa: 2020-09-09

Membros da banca

Yoshiharu Kohayakawa; Mrinal Kumar; Benjamin Evan Rossman

• Orientador: Yoshiharu Kohayakawa

Resumo

Alexander Razborov (1985) desenvolveu o método das aproximações para obter cotas inferiores para o tamanho de circuitos monótonos que decidem se um grafo contém uma clique. Dado um circuito monótono \"pequeno\", essa técnica consiste em encontrar uma função Booleana monótona que aproxima o circuito numa distribuição de interesse, mas comete erros de computação nessa mesma distribuição. Para provar que tal função é de fato uma boa aproximação, Razborov utilizou o lema dos girassóis de Erd\\Hs e Rado (1960). Essa técnica foi aprimorada por Alon e Boppana (1987) para mostrar cotas inferiores para uma gama muito maior de problemas computacionais monótonos. Nesse trabalho, os autores também melhoraram o resultado de Razborov para o problema da clique, utilizando uma variação relaxada de girassóis. Mais recentemente, Rossman (2010) desenvolveu uma outra variação de girassóis, hoje chamada de \"girassóis robustos\", para obter cotas inferiores para o problema da clique em grafos aleatórios. Em seguida, o conceito de girassóis robustos encontrou aplicações em várias áreas da complexidade computacional, tais como esparsificação de DNFs, extratores de aleatoriedade e teoremas de \"lifting\". Ainda mais recente foi um resultado impactante de Alweiss, Lovett, Wu e Zhang (2020), que mostrou cotas melhores que a de Rossman para girassóis robustos. Esse resultado foi utilizado para obter o progresso mais significativo na conjectura dos girassóis desde a sua origem em 1960. Nesse trabalho, vamos mostrar como os desenvolvimentos recentes em teoremas de girassol podem ser aplicados para melhorar cotas inferiores para circuitos monótonos. Em particular, vamos mostrar a melhor cota inferior para um circuito monótono obtida até o momento, quebrando um recorde de 20 anos obtido por Harnik e Raz (2000). Iremos também melhorar a cota inferior de Alon e Boppana para a função clique numa faixa levemente mais restrita de tamanhos de clique. (AU)

• Processo FAPESP: 18/05557-7 - Complexidade computacional e combinatória extremal
• Beneficiário: Bruno Pasqualotto Cavalar
• Modalidade de apoio: Bolsas no Brasil - Mestrado