Monotone Circuit Lower Bounds from Robust Sunflowers

Robust sunflowers are a generalization of combinatorial sunflowers that have applications in monotone circuit complexity Rossman (SIAM J. Comput. 43:256–279, 2014), DNF sparsification Gopalan et al. (Comput. Complex. 22:275–310 2013), randomness extractors Li et al. (In: APPROX-RANDOM, LIPIcs 116:51...

Descripción completa

Detalles Bibliográficos
Autores principales: Cavalar, Bruno Pasqualotto, Kumar, Mrinal, Rossman, Benjamin
Formato: Online Artículo Texto
Lenguaje:English
Publicado: Springer US 2022
Materias:
Article
Acceso en línea:https://www.ncbi.nlm.nih.gov/pmc/articles/PMC9705498/
https://www.ncbi.nlm.nih.gov/pubmed/36465838
http://dx.doi.org/10.1007/s00453-022-01000-3

Internet

https://www.ncbi.nlm.nih.gov/pmc/articles/PMC9705498/
https://www.ncbi.nlm.nih.gov/pubmed/36465838
http://dx.doi.org/10.1007/s00453-022-01000-3

Ejemplares similares