Dissertação de Mestrado
DOI
https://doi.org/10.11606/D.45.2020.tde-25112020-162107
Documento
Autor
Nome completo
Bruno Pasqualotto Cavalar
E-mail
Unidade da USP
Área do Conhecimento
Data de Defesa
Imprenta
São Paulo, 2020
Orientador
Banca examinadora
Kohayakawa, Yoshiharu (Presidente)
Kumar, Mrinal
Rossman, Benjamin Evan
Título em inglês
Sunflowers theorems in computational complexity
Palavras-chave em inglês
Circuit complexity
Combinatorics
Computational complexity
Extremal combinatorics
Extremal set theory
Monotone circuit complexity
Probabilistic combinatorics
Sunflowers
Resumo em inglês
Alexander Razborov (1985) developed the approximation method to obtain lower bounds on the size of monotone circuits deciding if a graph contains a clique. Given a small circuit, this technique consists in finding a monotone Boolean function which approximates the circuit in a distribution of interest, but makes computation errors in that same distribution. To prove that such a function is indeed a good approximation, Razborov used the sunflower lemma of Erds and Rado (1960). This technique was improved by Alon and Boppana (1987) to show lower bounds for a larger class of monotone computational problems. In that same work, the authors also improved the result of Razborov for the clique problem, using a relaxed variant of sunflowers. More recently, Rossman (2010) developed another variant of sunflowers, now called robust sunflowers, to obtain lower bounds for the clique problem in random graphs. In the following years, the concept of robust sunflowers found applications in many areas of computational complexity, such as DNF sparsification, randomness extractors and lifting theorems. Even more recent was the breakthrough result of Alweiss, Lovett, Wu and Zhang (2020), which improved Rossmans bound on the size of hypergraphs without robust sunflowers. This result was employed to obtain the most significant progress on the sunflower conjecture since its inception in 1960. In this work, we will show how the recent progresses in sunflower theorems can be applied to improve monotone circuit lower bounds. In particular, we will show the best monotone circuit lower bound obtained up to now, thus breaking a 20-year old record of Harnik and Raz (2000). We will also improve the lower bound of Alon and Boppana for the clique function in a slightly more restricted range of clique sizes.
Título em português
Teoremas de girassol em complexidade computacional
Palavras-chave em português
Combinatória
Combinatória extremal
Combinatória probabilistica
Complexidade computational
Complexidade de circuitos
Complexidade de circuitos monótonos
Girassóis
Teoria extremal dos conjuntos
Resumo em português
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.
AVISO - A consulta a este documento fica condicionada na aceitação das seguintes condições de uso:
Este trabalho é somente para uso privado de atividades de pesquisa e ensino. Não é autorizada sua reprodução para quaisquer fins lucrativos. Esta reserva de direitos abrange a todos os dados do documento bem como seu conteúdo. Na utilização ou citação de partes do documento é obrigatório mencionar nome da pessoa autora do trabalho.
thesis.pdf (1,023.19 Kbytes)
Data de Publicação
2020-11-27