• JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
 
  Bookmark and Share
 
 
Disertación de Maestría
DOI
https://doi.org/10.11606/D.45.2020.tde-25112020-162107
Documento
Autor
Nombre completo
Bruno Pasqualotto Cavalar
Dirección Electrónica
Instituto/Escuela/Facultad
Área de Conocimiento
Fecha de Defensa
Publicación
São Paulo, 2020
Director
Tribunal
Kohayakawa, Yoshiharu (Presidente)
Kumar, Mrinal
Rossman, Benjamin Evan
Título en inglés
Sunflowers theorems in computational complexity
Palabras clave en inglés
Circuit complexity
Combinatorics
Computational complexity
Extremal combinatorics
Extremal set theory
Monotone circuit complexity
Probabilistic combinatorics
Sunflowers
Resumen en 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 en portugués
Teoremas de girassol em complexidade computacional
Palabras clave en 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
Resumen en 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.
 
ADVERTENCIA - La consulta de este documento queda condicionada a la aceptación de las siguientes condiciones de uso:
Este documento es únicamente para usos privados enmarcados en actividades de investigación y docencia. No se autoriza su reproducción con finalidades de lucro. Esta reserva de derechos afecta tanto los datos del documento como a sus contenidos. En la utilización o cita de partes del documento es obligado indicar el nombre de la persona autora.
thesis.pdf (1,023.19 Kbytes)
Fecha de Publicación
2020-11-27
 
ADVERTENCIA: Aprenda que son los trabajos derivados haciendo clic aquí.
Todos los derechos de la tesis/disertación pertenecen a los autores
CeTI-SC/STI
Biblioteca Digital de Tesis y Disertaciones de la USP. Copyright © 2001-2022. Todos los derechos reservados.