Sunflowers theorems in computational complexity (2020)
- Authors:
- Autor USP: CAVALAR, BRUNO PASQUALOTTO - IME
- Unidade: IME
- Sigla do Departamento: MAC
- DOI: 10.11606/D.45.2020.tde-25112020-162107
- Assunto: COMBINATÓRIA PROBABILÍSTICA
- Keywords: Circuit complexity; Combinatória; Combinatória extremal; Combinatorics; Complexidade computational; Complexidade de circuitos monótonos; Computational complexity; Extremal combinatorics; Extremal set theory; Monotone circuit complexity; Probabilistic combinatorics; Teoria extremal dos conjuntos
- Agências de fomento:
- Language: Inglês
- Abstract: 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. Nessetrabalho, 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
- Imprenta:
- Data da defesa: 09.09.2020
- Status:
- Artigo publicado em periódico de acesso aberto (Gold Open Access)
- Versão do Documento:
- Versão publicada (Published version)
- Acessar versão aberta:
-
ABNT
CAVALAR, Bruno Pasqualotto. Sunflowers theorems in computational complexity. 2020. Dissertação (Mestrado) – Universidade de São Paulo, São Paulo, 2020. Disponível em: https://teses.usp.br/teses/disponiveis/45/45134/tde-25112020-162107/. Acesso em: 13 abr. 2026. -
APA
Cavalar, B. P. (2020). Sunflowers theorems in computational complexity (Dissertação (Mestrado). Universidade de São Paulo, São Paulo. Recuperado de https://teses.usp.br/teses/disponiveis/45/45134/tde-25112020-162107/ -
NLM
Cavalar BP. Sunflowers theorems in computational complexity [Internet]. 2020 ;[citado 2026 abr. 13 ] Available from: https://teses.usp.br/teses/disponiveis/45/45134/tde-25112020-162107/ -
Vancouver
Cavalar BP. Sunflowers theorems in computational complexity [Internet]. 2020 ;[citado 2026 abr. 13 ] Available from: https://teses.usp.br/teses/disponiveis/45/45134/tde-25112020-162107/
Informações sobre a disponibilidade de versões do artigo em acesso aberto coletadas automaticamente via oaDOI API (Unpaywall).
Por se tratar de integração com serviço externo, podem existir diferentes versões do trabalho (como preprints ou postprints), que podem diferir da versão publicada.
How to cite
A citação é gerada automaticamente e pode não estar totalmente de acordo com as normas
