Autor(es)

Cavalar, Bruno Pasqualotto ; Kumar, Mrinal ; Rossman, Benjamin

• Tipo de documento: Artigo Científico
• Fonte: LATIN 2020: THEORETICAL INFORMATICS; v. 12118, p. 12-pg., 2020-01-01.

Resumo

Robust sunflowers are a generalization of combinatorial sunflowers that have applications in monotone circuit complexity [14], DNF sparsification [6], randomness extractors [8], and recent advances on the Erdos-Rado sunflower conjecture [3,9,12]. The recent breakthrough of Alweiss, Lovett, Wu and Zhang [3] gives an improved bound on the maximum size of a w-set system that excludes a robust sunflower. In this paper, we use this result to obtain an exp(n(1/2-o(1))) lower bound on the monotone circuit size of an explicit n-variate monotone function, improving the previous record exp(n(1/3-o(1))) of Harnik and Raz [7]. We also show an exp(Omega(n)) lower bound on the monotone arithmetic circuit size of a related polynomial. Finally, we introduce a notion of robust clique-sunflowers and use this to prove an n(Omega(k)) lower bound on the monotone circuit size of the CLIQUE function for all k <= n(1/3-o(1)), strengthening the bound of Alon and Boppana [1]. (AU)

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