{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,23]],"date-time":"2026-08-23T17:15:26Z","timestamp":1787505326720,"version":"build-2736575974"},"publisher-location":"New York, NY, USA","reference-count":40,"publisher":"ACM","license":[{"start":{"date-parts":[[2020,6,22]],"date-time":"2020-06-22T00:00:00Z","timestamp":1592784000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100007515","name":"National Science Foundation","doi-asserted-by":"publisher","award":["1763299,1614023"],"award-info":[{"award-number":["1763299,1614023"]}],"id":[{"id":"10.13039\/100007515","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2020,6,22]]},"DOI":"10.1145\/3357713.3384234","type":"proceedings-article","created":{"date-parts":[[2020,6,6]],"date-time":"2020-06-06T21:45:25Z","timestamp":1591479925000},"page":"624-630","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":25,"title":["Improved bounds for the sunflower lemma"],"prefix":"10.1145","author":[{"given":"Ryan","family":"Alweiss","sequence":"first","affiliation":[{"name":"Princeton University, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Shachar","family":"Lovett","sequence":"additional","affiliation":[{"name":"University of California at San Diego, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Kewen","family":"Wu","sequence":"additional","affiliation":[{"name":"Peking University, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Jiapeng","family":"Zhang","sequence":"additional","affiliation":[{"name":"Harvard University, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2020,6,22]]},"reference":[{"key":"e_1_3_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1137\/0219074"},{"key":"e_1_3_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00037-013-0060-1"},{"key":"e_1_3_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1002\/0471722154"},{"key":"e_1_3_2_1_4_1","volume-title":"41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016 ). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik.","author":"Balaji Nikhil","unstructured":"Nikhil Balaji , Samir Datta , Raghav Kulkarni , and Supartha Podder . 2016. Graph Properties in Node-Query Setting: Efect of Breaking Symmetry . In 41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016 ). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik. Nikhil Balaji, Samir Datta, Raghav Kulkarni, and Supartha Podder. 2016. Graph Properties in Node-Query Setting: Efect of Breaking Symmetry. In 41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016 ). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik."},{"key":"e_1_3_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.1997.0905"},{"key":"e_1_3_2_1_6_1","unstructured":"Bruno Pasqualotto Cavalar Mrinal Kumar and Benjamin Rossman. 2020. Monotone Circuit Lower Bounds from Robust Sunflowers.  Bruno Pasqualotto Cavalar Mrinal Kumar and Benjamin Rossman. 2020. Monotone Circuit Lower Bounds from Robust Sunflowers."},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-21275-3"},{"key":"e_1_3_2_1_8_1","doi-asserted-by":"crossref","unstructured":"Dana Dachman-Soled Mukul Kulkarni and Aria Shahverdi. 2019. Tight upper and lower bounds for leakage-resilient locally decodable and updatable nonmalleable codes. Information and Computation ( 2019 ).  Dana Dachman-Soled Mukul Kulkarni and Aria Shahverdi. 2019. Tight upper and lower bounds for leakage-resilient locally decodable and updatable nonmalleable codes. Information and Computation ( 2019 ).","DOI":"10.1016\/j.ic.2019.05.001"},{"key":"e_1_3_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973099.6"},{"key":"e_1_3_2_1_10_1","doi-asserted-by":"crossref","unstructured":"Michel Deza and Peter Frankl. 1981. Every large set of equidistant (0 +1 \u22121)-vectors forms a sunflower. Combinatorica 1 3 ( 1981 ) 225-231.  Michel Deza and Peter Frankl. 1981. Every large set of equidistant (0 +1 \u22121)-vectors forms a sunflower. Combinatorica 1 3 ( 1981 ) 225-231.","DOI":"10.1007\/BF02579328"},{"key":"e_1_3_2_1_11_1","doi-asserted-by":"crossref","unstructured":"Irit Dinur and Samuel Safra. 2005. On the hardness of approximating minimum vertex cover. Annals of mathematics ( 2005 ) 439-485.  Irit Dinur and Samuel Safra. 2005. On the hardness of approximating minimum vertex cover. Annals of mathematics ( 2005 ) 439-485.","DOI":"10.4007\/annals.2005.162.439"},{"key":"e_1_3_2_1_12_1","volume-title":"Parameterized complexity","author":"Downey Rodney G","unstructured":"Rodney G Downey and Michael Ralph Fellows . 2012. Parameterized complexity . Springer Science & Business Media . Rodney G Downey and Michael Ralph Fellows. 2012. Parameterized complexity. Springer Science & Business Media."},{"key":"e_1_3_2_1_13_1","article-title":"Intersection theorems for systems of sets","volume":"35","author":"Erd\u0151s Paul","year":"1960","unstructured":"Paul Erd\u0151s and Richard Rado . 1960 . Intersection theorems for systems of sets . Journal of the London Mathematical Society 35 , 1 ( 1960 ), 85-90. Paul Erd\u0151s and Richard Rado. 1960. Intersection theorems for systems of sets. Journal of the London Mathematical Society 35, 1 ( 1960 ), 85-90.","journal-title":"Journal of the London Mathematical Society"},{"key":"e_1_3_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-29953-X"},{"key":"e_1_3_2_1_15_1","article-title":"Dynamic word problems","volume":"44","author":"Frandsen Gudmund Skovbjerg","year":"1997","unstructured":"Gudmund Skovbjerg Frandsen , Peter Bro Miltersen , and Sven Skyum . 1997 . Dynamic word problems . J. ACM 44 , 2 ( 1997 ), 257-271. Gudmund Skovbjerg Frandsen, Peter Bro Miltersen, and Sven Skyum. 1997. Dynamic word problems. J. ACM 44, 2 ( 1997 ), 257-271.","journal-title":"J. ACM"},{"key":"e_1_3_2_1_16_1","volume-title":"Thresholds Versus Fractional Expectation-Thresholds. arXiv preprint arXiv","author":"Frankston Keith","year":"1910","unstructured":"Keith Frankston , Jef Kahn , Bhargav Narayanan , and Jinyoung Park . 2019. Thresholds Versus Fractional Expectation-Thresholds. arXiv preprint arXiv : 1910 . 13433 ( 2019 ). Keith Frankston, Jef Kahn, Bhargav Narayanan, and Jinyoung Park. 2019. Thresholds Versus Fractional Expectation-Thresholds. arXiv preprint arXiv: 1910. 13433 ( 2019 )."},{"key":"e_1_3_2_1_17_1","volume-title":"Improved Bound on Sets Including No Sunflower with Three Petals. arXiv preprint arXiv","author":"Fukuyama Junichiro","year":"1809","unstructured":"Junichiro Fukuyama . 2018. Improved Bound on Sets Including No Sunflower with Three Petals. arXiv preprint arXiv : 1809 . 10318 ( 2018 ). Junichiro Fukuyama. 2018. Improved Bound on Sets Including No Sunflower with Three Petals. arXiv preprint arXiv: 1809. 10318 ( 2018 )."},{"key":"e_1_3_2_1_18_1","doi-asserted-by":"crossref","unstructured":"Anna G\u00e1l and Peter Bro Miltersen. 2007. The cell probe complexity of succinct data structures. Theoretical Computer Science 379 3 ( 2007 ) 405-417.  Anna G\u00e1l and Peter Bro Miltersen. 2007. The cell probe complexity of succinct data structures. Theoretical Computer Science 379 3 ( 2007 ) 405-417.","DOI":"10.1016\/j.tcs.2007.02.047"},{"key":"e_1_3_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2006.27"},{"key":"e_1_3_2_1_20_1","doi-asserted-by":"crossref","unstructured":"Parikshit Gopalan Raghu Meka and Omer Reingold. 2013. DNF sparsification and a faster deterministic counting algorithm. Computational Complexity 22 2 ( 2013 ) 275-310.  Parikshit Gopalan Raghu Meka and Omer Reingold. 2013. DNF sparsification and a faster deterministic counting algorithm. Computational Complexity 22 2 ( 2013 ) 275-310.","DOI":"10.1007\/s00037-013-0068-6"},{"key":"e_1_3_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1016\/0166-218X(90)90082-N"},{"key":"e_1_3_2_1_22_1","volume-title":"Computational limitations of small-depth circuits","author":"H\u00e5stad Johan","unstructured":"Johan H\u00e5stad . 1987. Computational limitations of small-depth circuits . MIT Press , Cambridge, MA, USA . Johan H\u00e5stad. 1987. Computational limitations of small-depth circuits. MIT Press, Cambridge, MA, USA."},{"key":"e_1_3_2_1_23_1","doi-asserted-by":"crossref","unstructured":"Ishay Haviv and Ning Xie. 2017. Sunflowers and testing triangle-freeness of functions. computational complexity 26 2 ( 2017 ) 497-530.  Ishay Haviv and Ning Xie. 2017. Sunflowers and testing triangle-freeness of functions. computational complexity 26 2 ( 2017 ) 497-530.","DOI":"10.1007\/s00037-016-0138-7"},{"key":"e_1_3_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.5555\/2722129.2722171"},{"key":"e_1_3_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.disc.2009.07.011"},{"key":"e_1_3_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/3341106"},{"key":"e_1_3_2_1_27_1","volume-title":"A bound of the cardinality of families not containing \u2206-systems","author":"Kostochka AV","unstructured":"AV Kostochka . 1997. A bound of the cardinality of families not containing \u2206-systems . In The Mathematics of Paul Erd\u0151s II. Springer , 229-235. AV Kostochka. 1997. A bound of the cardinality of families not containing \u2206-systems. In The Mathematics of Paul Erd\u0151s II. Springer, 229-235."},{"key":"e_1_3_2_1_28_1","unstructured":"Xin Li Shachar Lovett and Jiapeng Zhang. 2018. Sunflowers and quasi-sunflowers from randomness extractors. In Approximation Randomization and Combinatorial Optimization. Algorithms and Techniques (APPROX\/RANDOM 2018 ). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik.  Xin Li Shachar Lovett and Jiapeng Zhang. 2018. Sunflowers and quasi-sunflowers from randomness extractors. In Approximation Randomization and Combinatorial Optimization. Algorithms and Techniques (APPROX\/RANDOM 2018 ). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik."},{"key":"e_1_3_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.CCC.2019.5"},{"key":"e_1_3_2_1_30_1","unstructured":"Shachar Lovett Kewen Wu and Jiapeng Zhang. 2019. Decision list compression by mild random restrictions. Electronic Colloquium on Computational Complexity (ECCC) 26 ( 2019 ) 137. https:\/\/eccc.weizmann. ac.il\/report\/2019\/137  Shachar Lovett Kewen Wu and Jiapeng Zhang. 2019. Decision list compression by mild random restrictions. Electronic Colloquium on Computational Complexity (ECCC) 26 ( 2019 ) 137. https:\/\/eccc.weizmann. ac.il\/report\/2019\/137"},{"key":"e_1_3_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/3313276.3316323"},{"key":"e_1_3_2_1_32_1","doi-asserted-by":"crossref","unstructured":"Michael Luby and Jessica Staddon. 1998. Combinatorial bounds for broadcast encryption. Advances in Cryptology\u00e2\u0102\u0164EUROCRYPT'98 ( 1998 ) 512-526.  Michael Luby and Jessica Staddon. 1998. Combinatorial bounds for broadcast encryption. Advances in Cryptology\u00e2\u0102\u0164EUROCRYPT'98 ( 1998 ) 512-526.","DOI":"10.1007\/BFb0054150"},{"key":"e_1_3_2_1_33_1","doi-asserted-by":"crossref","unstructured":"D\u00e1niel Marx. 2005. Parameterized complexity of constraint satisfaction problems. Computational Complexity 14 2 ( 2005 ) 153-183.  D\u00e1niel Marx. 2005. Parameterized complexity of constraint satisfaction problems. Computational Complexity 14 2 ( 2005 ) 153-183.","DOI":"10.1007\/s00037-005-0195-9"},{"key":"e_1_3_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/1060590.1060606"},{"key":"e_1_3_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-44647-8_3"},{"key":"e_1_3_2_1_36_1","volume-title":"33rd Computational Complexity Conference (CCC 2018 ). Schloss Dagstuhl-LeibnizZentrum fuer Informatik.","author":"Ramamoorthy Sivaramakrishnan Natarajan","year":"2018","unstructured":"Sivaramakrishnan Natarajan Ramamoorthy and Anup Rao . 2018 . Lower bounds on non-adaptive data structures maintaining sets of numbers, from sunflowers . In 33rd Computational Complexity Conference (CCC 2018 ). Schloss Dagstuhl-LeibnizZentrum fuer Informatik. Sivaramakrishnan Natarajan Ramamoorthy and Anup Rao. 2018. Lower bounds on non-adaptive data structures maintaining sets of numbers, from sunflowers. In 33rd Computational Complexity Conference (CCC 2018 ). Schloss Dagstuhl-LeibnizZentrum fuer Informatik."},{"key":"e_1_3_2_1_37_1","volume-title":"Data Structuring Problems in the Bit Probe Model. Master's thesis","author":"Rahman Mohammad Ziaur","unstructured":"Mohammad Ziaur Rahman . 2007. Data Structuring Problems in the Bit Probe Model. Master's thesis . University of Waterloo . Mohammad Ziaur Rahman. 2007. Data Structuring Problems in the Bit Probe Model. Master's thesis. University of Waterloo."},{"key":"e_1_3_2_1_38_1","volume-title":"Coding for Sunflowers. CoRR abs\/","author":"Rao Anup","year":"1909","unstructured":"Anup Rao . 2019. Coding for Sunflowers. CoRR abs\/ 1909 .04774 ( 2019 ). arXiv: 1909.04774 http:\/\/arxiv.org\/abs\/ 1909.04774 Anup Rao. 2019. Coding for Sunflowers. CoRR abs\/ 1909.04774 ( 2019 ). arXiv: 1909.04774 http:\/\/arxiv.org\/abs\/ 1909.04774"},{"key":"e_1_3_2_1_39_1","volume-title":"Bounded arithmetic and lower bounds in Boolean complexity","author":"Razborov Alexander A","unstructured":"Alexander A Razborov . 1995. Bounded arithmetic and lower bounds in Boolean complexity . In Feasible Mathematics II. Springer , 344-386. Alexander A Razborov. 1995. Bounded arithmetic and lower bounds in Boolean complexity. In Feasible Mathematics II. Springer, 344-386."},{"key":"e_1_3_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1137\/110839059"}],"event":{"name":"STOC '20: 52nd Annual ACM SIGACT Symposium on Theory of Computing","location":"Chicago IL USA","acronym":"STOC '20","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory"]},"container-title":["Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3357713.3384234","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3357713.3384234","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T18:41:12Z","timestamp":1750185672000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3357713.3384234"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,6,22]]},"references-count":40,"alternative-id":["10.1145\/3357713.3384234","10.1145\/3357713"],"URL":"https:\/\/doi.org\/10.1145\/3357713.3384234","relation":{},"subject":[],"published":{"date-parts":[[2020,6,22]]},"assertion":[{"value":"2020-06-22","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}