Sunflowers and Robust Sunflowers from Randomness Extractors

by Xin Li, Shachar Lovett, and Jiapeng Zhang

Theory of Computing, Volume 18(2), pp. 1-18, 2022

Bibliography with links to cited articles

[1]   Noga Alon, Amir Shpilka, and Christopher Umans: On sunflowers and matrix multiplication. Comput. Complexity, 22(2):219–243, 2013. Preliminary version in CCC’12. [doi:10.1007/s00037-013-0060-1, ECCC:TR11-067]

[2]   Ryan Alweiss, Shachar Lovett, Kewen Wu, and Jiapeng Zhang: Improved bounds for the sunflower lemma. Ann. Math., 194(3):795–815, 2021. Preliminary version in STOC’20. [doi:10.4007/annals.2021.194.3.5, ECCC:TR19-110, arXiv:1908.08483]

[3]   Boaz Barak, Guy Kindler, Ronen Shaltiel, Benny Sudakov, and Avi Wigderson: Simulating independence: New constructions of condensers, Ramsey graphs, dispersers, and extractors. J. ACM, 57(4):20:1–52, 2010. Preliminary version in STOC’05. [doi:10.1145/1734213.1734214, ECCC:TR10-037]

[4]   Avraham Ben-Aroya, Dean Doron, and Amnon Ta-Shma: An efficient reduction from two-source to non-malleable extractors: Achieving near-logarithmic min-entropy. In Proc. 49th STOC, pp. 1185–1194. ACM Press, 2017. [doi:10.1145/3055399.3055423, ECCC:TR16-088]

[5]   Eshan Chattopadhyay and David Zuckerman: Explicit two-source extractors and resilient functions. In Proc. 48th STOC, pp. 670–683. ACM Press, 2016. [doi:10.1145/2897518.2897528, ECCC:TR15-119]

[6]   Benny Chor and Oded Goldreich: Unbiased bits from sources of weak randomness and probabilistic communication complexity. SIAM J. Comput., 17(2):230–261, 1988. Preliminary version in FOCS’85. [doi:10.1137/0217015]

[7]   Gil Cohen: Towards optimal two-source extractors and Ramsey graphs. In Proc. 49th STOC, pp. 1157–1170. ACM Press, 2017. [doi:10.1145/3055399.3055429, ECCC:TR16-114]

[8]   Ernie Croot, Vsevolod F. Lev, and Péter Pál Pach: Progression-free sets in Z4n are exponentially small. Ann. Math., 185(1):331–337, 2017. [doi:10.4007/annals.2017.185.1.7]

[9]   Jordan S. Ellenberg and Dion Gijswijt: On large subsets of Fqn with no three-term arithmetic progression. Ann. Math., 185(1):339–343, 2017. [doi:10.4007/annals.2017.185.1.8]

[10]   Paul Erdős: Some remarks on the theory of graphs. Bull. AMS, 53(4):292–294, 1947. project Euclid.

[11]   Paul Erdős and Richard Rado: Intersection theorems for systems of sets. J. London Math. Soc., 35(1):85–90, 1960. [doi:10.1112/jlms/s1-35.1.85]

[12]   Paul Erdős and George Szekeres: A combinatorial problem in geometry. Compositio Math., 2:463–470, 1935. NUMDAM.

[13]   Mika Göös, Shachar Lovett, Raghu Meka, Thomas Watson, and David Zuckerman: Rectangles are nonnegative juntas. SIAM J. Comput., 45(5):1835–1869, 2016. Preliminary version in STOC’15. [doi:10.1137/15M103145X, ECCC:TR14-147]

[14]   Parikshit Gopalan, Raghu Meka, and Omer Reingold: DNF sparsification and a faster deterministic counting algorithm. Comput. Complexity, 22(2):275–310, 2013. Preliminary version in CCC’12. [doi:10.1007/s00037-013-0068-6, arXiv:1205.3534]

[15]   Ben Green and Terence Tao: The primes contain arbitrarily long arithmetic progressions. Ann. Math., 167(2):481–547, 2008. [doi:10.4007/annals.2008.167.481]

[16]   Pravesh K. Kothari, Raghu Meka, and Prasad Raghavendra: Approximating rectangles by juntas and weakly-exponential lower bounds for LP relaxations of CSPs. In Proc. 49th STOC, pp. 590–603. ACM Press, 2017. [doi:10.1145/3055399.3055438, arXiv:1610.02704]

[17]   Xin Li: Three source extractors for polylogarithmic min-entropy. In Proc. 56th FOCS, pp. 863–882. IEEE Comp. Soc., 2015. [doi:10.1109/FOCS.2015.58, ECCC:TR15-034, arXiv:1503.02286]

[18]   Xin Li: Improved non-malleable extractors, non-malleable codes and independent source extractors. In Proc. 49th STOC, pp. 1144–1156. ACM Press, 2017. [doi:10.1145/3055399.3055486, ECCC:TR16-115, arXiv:1608.00127]

[19]   Xin Li, Shachar Lovett, and Jiapeng Zhang: Sunflowers and quasi-sunflowers from randomness extractors. In Proc. 22nd Internat. Conf. on Randomization and Computation (RANDOM’18), pp. 51:1–13. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, 2018. [doi:10.4230/LIPIcs.APPROX-RANDOM.2018.51]

[20]   Shachar Lovett, Noam Solomon, and Jiapeng Zhang: From DNF compression to sunflower theorems via regularity. In Proc. 34th Comput. Complexity Conf. (CCC’19), volume 137, pp. 5:1–14. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, 2019. [doi:10.4230/LIPIcs.CCC.2019.5, ECCC:TR19-028, arXiv:1903.00580]

[21]   Shachar Lovett, Kewen Wu, and Jiapeng Zhang: Decision list compression by mild random restrictions. In Proc. 52nd STOC, pp. 247–254. ACM Press, 2020. [doi:10.1145/3357713.3384241, ECCC:TR19-137, arXiv:1909.10658]

[22]   Shachar Lovett and Jiapeng Zhang: DNF sparsification beyond sunflowers. In Proc. 51st STOC, pp. 454–460. ACM Press, 2019. [doi:10.1145/3313276.3316323, ECCC:TR18-190]

[23]   Raghu Meka: Personal communication, 2018.

[24]   Eric Naslund and Will Sawin: Upper bounds for sunflower-free sets. In Forum of Mathematics, Sigma, volume 5. Cambridge Univ. Press, 2017. [doi:10.1017/fms.2017.12]

[25]   Anup Rao: Coding for sunflowers. Discrete Analysis, pp. 2:1–8, 2020. [doi:10.19086/da.11887, arXiv:1909.04774]

[26]   Alexander A. Razborov: Lower bounds for the monotone complexity of some Boolean functions. Dokl. Math., 31(4):354–357, 1985. Link at Math-Net.ru.

[27]   Benjamin Rossman: The monotone complexity of k-clique on random graphs. SIAM J. Comput., 43(1):256–279, 2014. Preliminary version in FOCS’10. [doi:10.1137/110839059]

[28]   Endre Szemerédi: On sets of integers containing no k elements in arithmetic progression. Acta Arithm., 27(1):199–245, 1975. DML PL.

[29]   Endre Szemerédi: Regular partitions of graphs. In Problèmes combinatoires et théorie des graphes (Proc. conf. Univ. Orsay 1976), volume 260, pp. 399–401. C.N.R.S., 1978.