Document Open Access Logo

Sunflowers and Quasi-Sunflowers from Randomness Extractors

Authors Xin Li, Shachar Lovett, Jiapeng Zhang

PDF
Thumbnail PDF

File

LIPIcs.APPROX-RANDOM.2018.51.pdf
  • Filesize: 472 kB
  • 13 pages

Document Identifiers

Author Details

Xin Li
  • Johns Hopkins University, Baltimore, USA
Shachar Lovett
  • University of California San Diego, La Jolla, USA
Jiapeng Zhang
  • University of California San Diego, La Jolla, USA

Funding

  • Li, Xin: Research supported by NSF award CCF-1617713
  • Lovett, Shachar: Research supported by NSF CCF-1614023
  • Zhang, Jiapeng: Research supported by NSF CCF-1614023

Cite As Get BibTex

Xin Li, Shachar Lovett, and Jiapeng Zhang. Sunflowers and Quasi-Sunflowers from Randomness Extractors. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 116, pp. 51:1-51:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018) https://doi.org/10.4230/LIPIcs.APPROX-RANDOM.2018.51

Abstract

The Erdös-Rado sunflower theorem (Journal of Lond. Math. Soc. 1960) is a fundamental result in combinatorics, and the corresponding sunflower conjecture is a central open problem. Motivated by applications in complexity theory, Rossman (FOCS 2010) extended the result to quasi-sunflowers, where similar conjectures emerge about the optimal parameters for which it holds.
In this work, we exhibit a surprising connection between the existence of sunflowers and quasi-sunflowers in large enough set systems, and the problem of constructing (or existing) certain randomness extractors. This allows us to re-derive the known results in a systematic manner, and to reduce the relevant conjectures to the problem of obtaining improved constructions of the randomness extractors.

Subject Classification

ACM Subject Classification
  • Theory of computation → Randomness, geometry and discrete structures
Keywords
  • Sunflower conjecture
  • Quasi-sunflowers
  • Randomness Extractors

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Noga Alon, Amir Shpilka, and Christopher Umans. On sunflowers and matrix multiplication. Computational Complexity, pages 214-223, 2012. Google Scholar
  2. Boaz Barak, Guy Kindler, Ronen Shaltiel, Benny Sudakov, and Avi Wigderson. Simulating independence: New constructions of condensers, ramsey graphs, dispersers, and extractors. In Proceedings of the thirty-seventh annual ACM symposium on Theory of computing, pages 1-10. ACM, 2005. Google Scholar
  3. Avraham Ben-Aroya, Dean Doron, and Amnon Ta-Shma. Explicit two-source extractors for near-logarithmic min-entropy. In Proceedings of the 49th Annual ACM Symposium on Theory of Computing, 2017. Google Scholar
  4. Eshan Chattopadhyay and David Zuckerman. Explicit two-source extractors and resilient functions. In Proceedings of the 48th Annual ACM Symposium on Theory of Computing, 2016. Google Scholar
  5. Benny Chor and Oded Goldreich. Unbiased bits from sources of weak randomness and probabilistic communication complexity. SIAM Journal on Computing, 17(2):230-261, 1988. Google Scholar
  6. Gil Cohen. Two-source extractors for quasi-logarithmic min-entropy and improved privacy amplification protocols. In Proceedings of the 49th Annual ACM Symposium on Theory of Computing, 2017. Google Scholar
  7. Ernie Croot, Vsevolod F. Lev, and Péter Pál Pach. Progression-free sets in z₄ⁿ are exponentially small. Annals of Mathematics, 185(1):331-337, 2017. Google Scholar
  8. Paul Erdős. Some remarks on the theory of graphs. Bull. Amer. Math. Soc., 53(4):292-294, 1947. Google Scholar
  9. Paul Erdős and R Rado. Intersection theorems for systems of sets. Journal of the London Mathematical Society, 35(1):85-90, 1960. Google Scholar
  10. Paul Erdős and George Szekeres. A combinatorial problem in geometry. Compositio Mathematica, 2:463-470, 1935. Google Scholar
  11. M. Goos, S. Lovett, R. Meka, T. Watson, and D. Zuckerman. Rectangles are nonnegative juntas. SIAM Journal on Computing, 45(5):1835-1869, 2016. Google Scholar
  12. Parikshit Gopalan, Raghu Meka, and Omer Reingold. Dnf sparsification and a faster deterministic counting algorithm. computational complexity, 22(2):275-310, 2013. Google Scholar
  13. Ben Green and Terence Tao. The primes contain arbitrarily long arithmetic progressions. Annals of Mathematics, 167(2):481-547, 2008. Google Scholar
  14. Pravesh K. Kothari, Raghu Meka, and Prasad Raghavendra. Approximating rectangles by juntas and weakly-exponential lower bounds for lp relaxations of csps. In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, 2017. Google Scholar
  15. Xin Li. Three source extractors for polylogarithmic min-entropy. In Proceedings of the 56th Annual IEEE Symposium on Foundations of Computer Science, 2015. Google Scholar
  16. Xin Li. Improved non-malleable extractors, non-malleable codes and independent source extractors. In Proceedings of the 49th Annual ACM Symposium on Theory of Computing, 2017. Google Scholar
  17. Alexander Razborov. Some lower bounds for the monotone complexity of some boolean functions. Soviet Math. Dokl., 31:354-357, 1985. Google Scholar
  18. Benjamin Rossman. The monotone complexity of k-clique on random graphs. In Proceedings of the 2010 IEEE 51st Annual Symposium on Foundations of Computer Science, pages 193-201. IEEE Computer Society, 2010. Google Scholar
  19. Jordan S. Ellenberg and Dion Gijswijt. On large subsets of f_qⁿ with no three-term arithmetic progression. Annals of Mathematics, 185(1):339-343, 2017. Google Scholar
  20. Endre Szemerédi. On sets of integers containing no k elements in arithmetic progression. Acta Arithmetica, 27:199-245, 1975. Google Scholar
  21. Endre Szemerédi. Regular partitions of graphs. Problèmes combinatoires et théorie des graphes, 260:399-401, 1978. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact