11
$\begingroup$

In one lecture by Kewen Wu who is one of the authors of paper

Improved bounds for the sunflower lemma,

it is said that the sunflower lemma can be applied to many fields like

  1. circuit lower bounds
  2. data structure lower bounds
  3. matrix multiplication
  4. pseudorandomness
  5. cryptography
  6. property testing
  7. fixed parameter complexity

What I can know about the sunflower lemma comes from the books

Parameterized Complexity Theory

Extremal Combinatorics

The Mathematics of Paul Erdős II 2013

and papers

Improved Bound On Sets Including No Sunflower With Three Petals Junichiro Fukuyama 2018

Improved bounds for the sunflower lemma Ryan Alweiss, Shachar Lovett, Kewen Wu, Jiapeng Zhang 2019

How is it applied to the field of computer science?

Improve this question
$\endgroup$
7
  • $\begingroup$ What is the application in parametrized complexity? $\endgroup$
    – Turbo
    Mar 24, 2020 at 6:17
  • 2
    $\begingroup$ Hi, thanks for your interest in our work. We have some extra references on these applications in our stoc final version, which should be out in a few weeks. $\endgroup$
    – Shlw Kevin
    Mar 24, 2020 at 9:35
  • 1
    $\begingroup$ In parametrized complexity, the sunflowers can be used in the kernelization of the hitting set problem. And thank you for your work! $\endgroup$
    – Bubble
    Mar 24, 2020 at 13:56
  • 1
    $\begingroup$ @Bubble I hope that the answers currently given fit with your expectations... Judging from your comment on the hitting set problem, you already know about at least one example of how this is applied to computer science: in this case to a question in fixed parameter tractability, which is a subfield of algorithmics, and thus of (theoretical) computer science. What kind of answer are you expecting? Are you looking for a collection of further concrete examples, possibly along with references, where the sunflower lemma is applied in TCS - or maybe something different? $\endgroup$
    – Hermann Gruber
    Mar 29, 2020 at 20:07
  • 1
    $\begingroup$ @HermannGruber Non-malleable codes are definitely a cryptographic topic. $\endgroup$
    – Mark
    Mar 29, 2020 at 22:48

3 Answers 3

Reset to default
4
$\begingroup$

Sunflower lemma has applications in data structure lower bounds(as mentioned above). For eg. see: Lower Bounds on Non-Adaptive Data Structures Maintaining Sets of Numbers, from Sunflowers.

Improve this answer
$\endgroup$
4
$\begingroup$

Razborov's lower bound on the size of monotone boolean circuits for the clique problem is an early application in TCS.  A. A. Razborov, Some lower bounds for the monotone complexity of some Boolean functions, Soviet Math. Dokl. 31 (1985), 354-357. A good reference for learning about this is chapter 9 in Jukna's book "Boolean Function Complexity: Advances and Frontiers": http://www.thi.cs.uni-frankfurt.de/~jukna/boolean/Chapter9.pdf

Improve this answer
$\endgroup$
4
$\begingroup$

Håstad, Jukna, and Pudlák used the sunflower lemma to prove lower bounds on depth-$3$ $AC^0$ circuits: http://www.csc.kth.se/~johanh/topdowndepth3.pdf

This is also explained in Section 6.3 of the book of Jukna on extremal combinatorics, and in Section 11.3 of his book on boolean function complexity.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.