Amazing: Ryan Alweiss, Shachar Lovett, Kewen Wu, Jiapeng Zhang made dramatic progress on the Sunflower Conjecture

WOW! The new paper improved bounds for the sunflower lemma gives the most dramatic progress on the sunflower conjecture since it was asked. Congratulations to Ryan Alweiss, Shachar Lovett, Kewen Wu, Jiapeng Zhang.

(Written on my smartphone will expand it when reconnected to my laptop.)  (Reconnected) Rather, I will write about it again in a few weeks. Let me mention now that while the old difficult and ingenious improvements stayed in the neighborhood of Erdos and Rado initial upper bound the new result is in the neighborhood of the conjecture! (And is tight for a certain robust version of the problem!)

Let me also mention that we discussed the sunflower conjecture here many times and polymath10 (wiki pagefirst post, last post) was devoted to the problem.)

Update: Let me mention an important progress on the sunflower conjecture from 2018 by Junichiro Fukuyama in his paper Improved Bound on Sets Including No Sunflower with Three Petals. I missed Fukuyama’s paper at the time and I thank Sasha Kostochka and Andrew Thomason for telling me about it now.

This entry was posted in Combinatorics, Computer Science and Optimization. Bookmark the permalink.

9 Responses to Amazing: Ryan Alweiss, Shachar Lovett, Kewen Wu, Jiapeng Zhang made dramatic progress on the Sunflower Conjecture

  1. that kitty says:

    snuzzo wuzzo

  2. Pingback: Mohammad Ghomi and Joel Spruck settled the Cartan-Hadamard conjecture! | Combinatorics and more

  3. Gil Kalai says:

    Let me mention that the robust notion of the problem arose in the connection to problems in the theory of computing and in earlier works [3,2] and the proof strategy continues the works in [1,2].

    [1] X. Li, S. Lovett, and J. Zhang. 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, 2018.

    [2] S. Lovett, N. Solomon, and J. Zhang. From DNF compression to sunflower theorems via regularity. In 34th Computational Complexity Conference, CCC 2019, July 18-20, 2019, New Brunswick, NJ, USA., pages 5:1–5:14, 2019.

    [3] B. Rossman. The monotone complexity of k-clique on random graphs. SIAM J. Comput., 43(1):256–279, 2014.

  4. Pingback: Computer Science and its Impact on our Future | Combinatorics and more

  5. Gil Kalai says:

    Anup Rao presents a simplification of the original Alweiss, Lovett, Wu, and Zhang argument.

  6. Pingback: Noisy quantum circuits: how do we know that we have robust experimental outcomes at all? (And do we care?) | Combinatorics and more

  7. Gil Kalai says:

    An excellent Quanta Magazine article by Kevin Hartnett . I was interviewed by Kevin and truly enjoyed to tell about the sunflower conjecture and I remember that when I prepared to the interview I thought about 3 major aspects of this achievement that makes me happy and during the interview I thought about one more. (And these aspects have several sub-aspects). The 4 aspects were 1) that it is a famous and difficult problem in extremal combinatorics that stood as a major challenge for many decades, 2) that it has various applications and connections to other problems in extremal combinatorics and Ramsey theory, 3) the manifestation of the structure vs randomness idea which is central in combinatorics and other areas 4) the old and new two-ways connections with the theory of computation – matrix multiplication, monotone lower bounds, improvement of the switching lemma fir pseudorandom circuits, and more.

    Of course it is a natural question if the methods can be used to prove the full conjecture, but for me the notion of robust sunflowers and the theorem for them which is sharp is very appealing.

  8. Pingback: Amazing! Keith Frankston, Jeff Kahn, Bhargav Narayanan, Jinyoung Park: Thresholds versus fractional expectation-thresholds | Combinatorics and more

  9. Pingback: Two talks at HUJI: on the “infamous lower tail” and TOMORROW on recent advances in combinatorics | Combinatorics and more

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s