{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T03:42:05Z","timestamp":1740109325352,"version":"3.37.3"},"reference-count":30,"publisher":"Springer Science and Business Media LLC","issue":"12","license":[{"start":{"date-parts":[[2022,7,14]],"date-time":"2022-07-14T00:00:00Z","timestamp":1657756800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2022,7,14]],"date-time":"2022-07-14T00:00:00Z","timestamp":1657756800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100001807","name":"Funda\u00e7\u00e3o de Amparo \u00e0 Pesquisa do Estado de S\u00e3o Paulo","doi-asserted-by":"publisher","award":["18\/05557-7","18\/22257-7"],"award-info":[{"award-number":["18\/05557-7","18\/22257-7"]}],"id":[{"id":"10.13039\/501100001807","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100002790","name":"Canadian Network for Research and Innovation in Machining Technology, Natural Sciences and Engineering Research Council of Canada","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100002790","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000879","name":"Alfred P. Sloan Foundation","doi-asserted-by":"publisher","id":[{"id":"10.13039\/100000879","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2022,12]]},"abstract":"Abstract<\/jats:title>Robust sunflowers are a generalization of combinatorial sunflowers that have applications in monotone circuit complexity Rossman (SIAM J. Comput. 43:256\u2013279, 2014), DNF sparsification Gopalan et\u00a0al. (Comput. Complex. 22:275\u2013310 2013), randomness extractors Li et\u00a0al. (In: APPROX-RANDOM, LIPIcs 116:51:1\u201313, 2018), and recent advances on the Erd\u0151s-Rado sunflower conjecture Alweiss et\u00a0al. (In: Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, STOC. Association for Computing Machinery, New York, NY, USA, 2020) Lovett et\u00a0al. (From dnf compression to sunflower theorems via regularity, 2019) Rao (Discrete Anal. 8,2020). The recent breakthrough of Alweiss, Lovett, Wu and Zhang Alweiss et\u00a0al. (In: Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, STOC. Association for Computing Machinery, New York, NY, USA, 2020) gives an improved bound on the maximum size of a w<\/jats:italic>-set system that excludes a robust sunflower. In this paper, we use this result to obtain an $$\\exp (n^{1\/2-o(1)})$$<\/jats:tex-math>\n \n exp<\/mml:mo>\n (<\/mml:mo>\n \n n<\/mml:mi>\n \n 1<\/mml:mn>\n \/<\/mml:mo>\n 2<\/mml:mn>\n -<\/mml:mo>\n o<\/mml:mi>\n (<\/mml:mo>\n 1<\/mml:mn>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:msup>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> lower bound on the monotone circuit size of an explicit n<\/jats:italic>-variate monotone function, improving the previous best known $$\\exp (n^{1\/3-o(1)})$$<\/jats:tex-math>\n \n exp<\/mml:mo>\n (<\/mml:mo>\n \n n<\/mml:mi>\n \n 1<\/mml:mn>\n \/<\/mml:mo>\n 3<\/mml:mn>\n -<\/mml:mo>\n o<\/mml:mi>\n (<\/mml:mo>\n 1<\/mml:mn>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:msup>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> due to Andreev (Algebra and Logic, 26:1\u201318, 1987) and Harnik and Raz (In: Proceedings of the Thirty-Second Annual ACM Symposium on Theory of Computing, ACM, New York, 2000). We also show an $$\\exp (\\varOmega (n))$$<\/jats:tex-math>\n \n exp<\/mml:mo>\n (<\/mml:mo>\n \u03a9<\/mml:mi>\n (<\/mml:mo>\n n<\/mml:mi>\n )<\/mml:mo>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> lower bound on the monotone arithmetic<\/jats:italic> circuit size of a related polynomial via a very simple proof. Finally, we introduce a notion of robust clique-sunflowers and use this to prove an $$n^{\\varOmega (k)}$$<\/jats:tex-math>\n \n n<\/mml:mi>\n \n \u03a9<\/mml:mi>\n (<\/mml:mo>\n k<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:msup>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> lower bound on the monotone circuit size of the CLIQUE function for all $$k \\leqslant n^{1\/3-o(1)}$$<\/jats:tex-math>\n \n k<\/mml:mi>\n \u2a7d<\/mml:mo>\n \n n<\/mml:mi>\n \n 1<\/mml:mn>\n \/<\/mml:mo>\n 3<\/mml:mn>\n -<\/mml:mo>\n o<\/mml:mi>\n (<\/mml:mo>\n 1<\/mml:mn>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:msup>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula>, strengthening the bound of Alon and Boppana (Combinatorica, 7:1\u201322, 1987).<\/jats:p>","DOI":"10.1007\/s00453-022-01000-3","type":"journal-article","created":{"date-parts":[[2022,7,14]],"date-time":"2022-07-14T06:02:43Z","timestamp":1657778563000},"page":"3655-3685","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Monotone Circuit Lower Bounds from Robust Sunflowers"],"prefix":"10.1007","volume":"84","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-0458-8767","authenticated-orcid":false,"given":"Bruno Pasqualotto","family":"Cavalar","sequence":"first","affiliation":[]},{"given":"Mrinal","family":"Kumar","sequence":"additional","affiliation":[]},{"given":"Benjamin","family":"Rossman","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2022,7,14]]},"reference":[{"issue":"4","key":"1000_CR1","doi-asserted-by":"publisher","first-page":"567","DOI":"10.1016\/0196-6774(86)90019-2","volume":"7","author":"N Alon","year":"1986","unstructured":"Alon, N., Babai, L., Itai, A.: A fast and simple randomized parallel algorithm for the maximal independent set problem. J. Algorithms 7(4), 567\u2013583 (1986). https:\/\/doi.org\/10.1016\/0196-6774(86)90019-2","journal-title":"J. Algorithms"},{"issue":"1","key":"1000_CR2","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/BF02579196","volume":"7","author":"N Alon","year":"1987","unstructured":"Alon, N., Boppana, R.B.: The monotone circuit complexity of Boolean functions. Combinatorica 7(1), 1\u201322 (1987)","journal-title":"Combinatorica"},{"key":"1000_CR3","doi-asserted-by":"publisher","unstructured":"Alweiss, R., Lovett, S., Wu, K., Zhang, J.: Improved bounds for the sunflower lemma. In: Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, STOC 2020, p 624\u2013630. Association for Computing Machinery, New York, NY, USA (2020). https:\/\/doi.org\/10.1145\/3357713.3384234","DOI":"10.1145\/3357713.3384234"},{"issue":"1","key":"1000_CR4","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/BF01978380","volume":"26","author":"A Andreev","year":"1987","unstructured":"Andreev, A.: A method for obtaining efficient lower bounds for monotone complexity. Algebra and Logic 26(1), 1\u201318 (1987)","journal-title":"Algebra and Logic"},{"issue":"5","key":"1000_CR5","first-page":"1033","volume":"282","author":"AE Andreev","year":"1985","unstructured":"Andreev, A.E.: A method for obtaining lower bounds on the complexity of individual monotone functions. Dokl. Akad. Nauk SSSR 282(5), 1033\u20131037 (1985)","journal-title":"Dokl. Akad. Nauk SSSR"},{"key":"1000_CR6","doi-asserted-by":"publisher","unstructured":"Bell, T., Chueluecha, S., Warnke, L.: Note on sunflowers. Discrete Mathematics 344(7), 112367 (2021). https:\/\/doi.org\/10.1016\/j.disc.2021.112367. https:\/\/www.sciencedirect.com\/science\/article\/pii\/S0012365X21000807","DOI":"10.1016\/j.disc.2021.112367"},{"key":"1000_CR7","doi-asserted-by":"publisher","unstructured":"Cohen, G., Haeupler, B., Schulman, L.J.: Explicit binary tree codes with polylogarithmic size alphabet. In: Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2018, p 535\u2013544. ACM. https:\/\/doi.org\/10.1145\/3188745.3188928. http:\/\/doi.acm.org\/10.1145\/3188745.3188928","DOI":"10.1145\/3188745.3188928"},{"key":"1000_CR8","doi-asserted-by":"publisher","first-page":"85","DOI":"10.1112\/jlms\/s1-35.1.85","volume":"35","author":"P Erd\u0151s","year":"1960","unstructured":"Erd\u0151s, P., Rado, R.: Intersection theorems for systems of sets. J. London Math. Soc. 35, 85\u201390 (1960)","journal-title":"J. London Math. Soc."},{"issue":"1","key":"1000_CR9","doi-asserted-by":"publisher","first-page":"211","DOI":"10.1007\/BF01884295","volume":"121","author":"A Garcia","year":"1995","unstructured":"Garcia, A., Stichtenoth, H.: A tower of artin-schreier extensions of function fields attaining the drinfeld-vladut bound. Inventiones Mathematicae 121(1), 211\u2013222 (1995)","journal-title":"Inventiones Mathematicae"},{"issue":"10","key":"1000_CR10","doi-asserted-by":"publisher","first-page":"A02","DOI":"10.1070\/SM2012v203n10ABEH004270","volume":"203","author":"SB Gashkov","year":"2012","unstructured":"Gashkov, S.B., Sergeev, I.: A method for deriving lower bounds for the complexity of monotone arithmetic circuits computing real polynomials. Sbornik: Mathematics 203(10), A02 (2012). https:\/\/doi.org\/10.1070\/SM2012v203n10ABEH004270","journal-title":"Sbornik: Mathematics"},{"issue":"2","key":"1000_CR11","doi-asserted-by":"publisher","first-page":"275","DOI":"10.1007\/s00037-013-0068-6","volume":"22","author":"P Gopalan","year":"2013","unstructured":"Gopalan, P., Meka, R., Reingold, O.: DNF sparsification and a faster deterministic counting algorithm. Comput. Complex. 22(2), 275\u2013310 (2013)","journal-title":"Comput. Complex."},{"key":"1000_CR12","doi-asserted-by":"publisher","unstructured":"Harnik, D., Raz, R.: Higher lower bounds on monotone size. In: Proceedings of the Thirty-Second Annual ACM Symposium on Theory of Computing, p 378\u2013387. ACM, New York (2000). https:\/\/doi.org\/10.1145\/335305.335349","DOI":"10.1145\/335305.335349"},{"issue":"2","key":"1000_CR13","doi-asserted-by":"publisher","first-page":"221","DOI":"10.1002\/rsa.3240010209","volume":"1","author":"S Janson","year":"1990","unstructured":"Janson, S.: Poisson approximation for large deviations. Random Structures and Algorithms 1(2), 221\u2013229 (1990)","journal-title":"Random Structures and Algorithms"},{"key":"1000_CR14","doi-asserted-by":"publisher","unstructured":"Janson, S., \u0141\u00a0uczak, T., Ruci\u0144ski, A.: Random graphs. Wiley-Interscience Series in Discrete Mathematics and Optimization. Wiley-Interscience, New York (2000). https:\/\/doi.org\/10.1002\/9781118032718. http:\/\/dx.doi.org\/10.1002\/9781118032718","DOI":"10.1002\/9781118032718"},{"key":"1000_CR15","doi-asserted-by":"publisher","unstructured":"Jerrum, M., Snir, M.: Some exact complexity results for straight-line computations over semirings. J. ACM 29(3), 874\u2013897 (1982). https:\/\/doi.org\/10.1145\/322326.322341. http:\/\/doi.acm.org\/10.1145\/322326.322341","DOI":"10.1145\/322326.322341"},{"issue":"1","key":"1000_CR16","doi-asserted-by":"publisher","first-page":"65","DOI":"10.1007\/s004930050046","volume":"19","author":"S Jukna","year":"1999","unstructured":"Jukna, S.: Combinatorics of monotone computations. Combinatorica 19(1), 65\u201385 (1999)","journal-title":"Combinatorica"},{"key":"1000_CR17","first-page":"51","volume":"116","author":"X Li","year":"2018","unstructured":"Li, X., Lovett, S., Zhang, J.: Sunflowers and quasi-sunflowers from randomness extractors. In: APPROX-RANDOM, LIPIcs 116, 51-1\u201313 (2018)","journal-title":"In: APPROX-RANDOM, LIPIcs"},{"key":"1000_CR18","unstructured":"Lovett, S., Solomon, N., Zhang, J.: From dnf compression to sunflower theorems via regularity. arXiv preprint arXiv:1903.00580 (2019)"},{"key":"1000_CR19","doi-asserted-by":"crossref","unstructured":"Lovett, S., Zhang, J.: Dnf sparsification beyond sunflowers. In: Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, p 454\u2013460. ACM (2019)","DOI":"10.1145\/3313276.3316323"},{"key":"1000_CR20","doi-asserted-by":"crossref","unstructured":"Pitassi, T., Robere, R.: Strongly exponential lower bounds for monotone computation. In: Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, p 1246\u20131255. ACM (2017)","DOI":"10.1145\/3055399.3055478"},{"key":"1000_CR21","unstructured":"Rao, A.: Coding for sunflowers. Discrete Anal. p Paper No. 2, 8 (2020). 10.19086\/da"},{"issue":"1","key":"1000_CR22","doi-asserted-by":"publisher","first-page":"167","DOI":"10.1016\/j.jcss.2010.06.013","volume":"77","author":"R Raz","year":"2011","unstructured":"Raz, R., Yehudayoff, A.: Multilinear formulas, maximal-partition discrepancy and mixed-sources extractors. J. Comput. Syst. Sci. 77(1), 167\u2013190 (2011). https:\/\/doi.org\/10.1016\/j.jcss.2010.06.013","journal-title":"J. Comput. Syst. Sci."},{"issue":"4","key":"1000_CR23","first-page":"798","volume":"281","author":"AA Razborov","year":"1985","unstructured":"Razborov, A.A.: Lower bounds on the monotone complexity of some Boolean functions. Dokl. Akad. Nauk SSSR 281(4), 798\u2013801 (1985)","journal-title":"Dokl. Akad. Nauk SSSR"},{"issue":"1","key":"1000_CR24","doi-asserted-by":"publisher","first-page":"256","DOI":"10.1137\/110839059","volume":"43","author":"B Rossman","year":"2014","unstructured":"Rossman, B.: The monotone complexity of $$k$$-clique on random graphs. SIAM J. Comput. 43(1), 256\u2013279 (2014). https:\/\/doi.org\/10.1137\/110839059","journal-title":"SIAM J. Comput."},{"key":"1000_CR25","unstructured":"Rossman, B.: Approximate sunflowers (2019). Unpublished, available at http:\/\/www.math.toronto.edu\/rossman\/approx-sunflowers.pdf"},{"key":"1000_CR26","unstructured":"Srinivasan, S.: Strongly exponential separation between monotone VP and monotone VNP. CoRR abs\/1903.01630 (2019). arXiv:1903.01630"},{"key":"1000_CR27","doi-asserted-by":"crossref","unstructured":"Stichtenoth, H.: Algebraic Function Fields and Codes, vol. 254. Springer Science & Business Media (2009)","DOI":"10.1007\/978-3-540-76878-4"},{"key":"1000_CR28","unstructured":"Tao, T.: The sunflower lemma via shannon entropy. Blogpost (2020). https:\/\/terrytao.wordpress.com\/2020\/07\/20\/the-sunflower-lemma-via-shannon-entropy\/"},{"key":"1000_CR29","doi-asserted-by":"publisher","first-page":"201","DOI":"10.1016\/0020-0190(84)90111-X","volume":"18","author":"J Tiekenheinrich","year":"1984","unstructured":"Tiekenheinrich, J.: A 4n-lower bound on the mononotone network complexity of a oneoutput boolean function. Information Processing Letters 18, 201\u2013201 (1984)","journal-title":"Information Processing Letters"},{"key":"1000_CR30","doi-asserted-by":"publisher","unstructured":"Yehudayoff, A.: Separating monotone VP and VNP. In: Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, STOC 2019, Phoenix, AZ, USA, June 23-26, 2019., p 425\u2013429 (2019). https:\/\/doi.org\/10.1145\/3313276.3316311","DOI":"10.1145\/3313276.3316311"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-022-01000-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00453-022-01000-3\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-022-01000-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,11,28]],"date-time":"2022-11-28T12:12:06Z","timestamp":1669637526000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00453-022-01000-3"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,7,14]]},"references-count":30,"journal-issue":{"issue":"12","published-print":{"date-parts":[[2022,12]]}},"alternative-id":["1000"],"URL":"https:\/\/doi.org\/10.1007\/s00453-022-01000-3","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"type":"print","value":"0178-4617"},{"type":"electronic","value":"1432-0541"}],"subject":[],"published":{"date-parts":[[2022,7,14]]},"assertion":[{"value":"19 March 2021","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"18 June 2022","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"14 July 2022","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors declare that they have no conflict of interest.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}}]}}