<p>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": <a href="http://www.thi.cs.uni-frankfurt.de/~jukna/boolean/Chapter9.pdf" rel="nofollow noreferrer">http://www.thi.cs.uni-frankfurt.de/~jukna/boolean/Chapter9.pdf</a> </p>

CC BY-SA 4.0
2020-03-28T22:32:35.647Z
2020-03-28T22:32:35.647Z
Hermann Gruber
<p>Sunflower lemma has applications in data structure lower bounds(as mentioned above). For eg. see:
<a href="https://eccc.weizmann.ac.il/report/2017/040/" rel="nofollow noreferrer">Lower Bounds on Non-Adaptive Data Structures Maintaining Sets of Numbers, from Sunflowers</a>.</p>

CC BY-SA 4.0
2020-03-28T18:07:21.457Z
2020-03-28T21:22:59.080Z
2020-03-28T21:22:59.080Z
A.2
<p>Håstad, Jukna, and Pudlák used the sunflower lemma to prove lower bounds on depth-<span class="math-container">$3$</span> <span class="math-container">$AC^0$</span> circuits:
<a href="http://www.csc.kth.se/~johanh/topdowndepth3.pdf" rel="nofollow noreferrer">http://www.csc.kth.se/~johanh/topdowndepth3.pdf</a></p>

<p>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.</p>

CC BY-SA 4.0
2020-03-29T09:03:08.077Z
2020-03-29T20:48:03.843Z
2020-03-29T20:48:03.843Z
Or Meir
<p>In one lecture by Kewen Wu who is one of the authors of paper </p>

<blockquote>
  <p><a href="https://arxiv.org/abs/1908.08483" rel="nofollow noreferrer">Improved bounds for the sunflower lemma</a>,</p>
</blockquote>

<p>it is said that the <strong>sunflower lemma</strong> can be applied to many fields like</p>

<ol>
<li>circuit lower bounds</li>
<li>data structure lower bounds</li>
<li>matrix multiplication</li>
<li>pseudorandomness</li>
<li>cryptography</li>
<li>property testing</li>
<li>fixed parameter complexity</li>
</ol>

<p>What I can know about the sunflower lemma comes from the books </p>

<blockquote>
  <p><a href="https://link.springer.com/book/10.1007/3-540-29953-X" rel="nofollow noreferrer">Parameterized Complexity Theory</a></p>
  
  <p><a href="https://link.springer.com/book/10.1007/978-3-642-17364-6" rel="nofollow noreferrer">Extremal Combinatorics</a> </p>
  
  <p><a href="https://link.springer.com/book/10.1007/978-3-642-60406-5" rel="nofollow noreferrer">The Mathematics of Paul Erdős II</a>     2013</p>
</blockquote>

<p>and papers </p>

<blockquote>
  <p><a href="https://arxiv.org/pdf/1809.10318.pdf" rel="nofollow noreferrer">Improved Bound On Sets Including No Sunflower
  With Three Petals</a> Junichiro Fukuyama 2018</p>
  
  <p><a href="https://arxiv.org/abs/1908.08483" rel="nofollow noreferrer">Improved bounds for the sunflower lemma</a> Ryan Alweiss, Shachar Lovett, Kewen Wu, Jiapeng Zhang 2019</p>
</blockquote>

<p>How is it applied to the field of computer science?</p>

CC BY-SA 4.0
2020-03-24T06:17:56.040Z
What is the application in parametrized complexity?
Turbo
CC BY-SA 4.0
2020-03-24T09:35:48.237Z
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.
Shlw Kevin
CC BY-SA 4.0
2020-03-24T13:56:08.367Z
In parametrized complexity,  the sunflowers can be used in the kernelization
of the hitting set problem. 
And thank you for your work!
Bubble
CC BY-SA 4.0
2020-03-25T11:23:25.217Z
What is the application in cryptography?
VS.
CC BY-SA 4.0
2020-03-29T20:07:10.583Z
@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?
Hermann Gruber
CC BY-SA 4.0
2020-03-29T20:16:56.070Z
@VS. possibly the following qualifies as an application in cryptography? https://eprint.iacr.org/2017/015.pdf Caveat emptor: I barely looked at it, and really don't know much about crypto. At least it talks about adversaries, plus it seems to make use of the Sunflower Lemma.
Hermann Gruber
CC BY-SA 4.0
2020-03-29T22:48:01.843Z
@HermannGruber Non-malleable codes are definitely a cryptographic topic.
Mark Schultz-Wu
<cc.complexity-theory><co.combinatorics><set-system>
Applications of sunflower lemma in theoretical computer science
Bubble
# Applications of sunflower lemma in theoretical computer science

(Asked by: username_0 on 2020-03-24)

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

> [Improved bounds for the sunflower lemma](https://arxiv.org/abs/1908.08483),

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](https://link.springer.com/book/10.1007/3-540-29953-X)
>
> [Extremal Combinatorics](https://link.springer.com/book/10.1007/978-3-642-17364-6)
>
> [The Mathematics of Paul Erdős II](https://link.springer.com/book/10.1007/978-3-642-60406-5) 2013

and papers

> [Improved Bound On Sets Including No Sunflower
> With Three Petals](https://arxiv.org/pdf/1809.10318.pdf) Junichiro Fukuyama 2018
>
> [Improved bounds for the sunflower lemma](https://arxiv.org/abs/1908.08483) Ryan Alweiss, Shachar Lovett, Kewen Wu, Jiapeng Zhang 2019

How is it applied to the field of computer science?

**Tags:** cc.complexity-theory, co.combinatorics, set-system
> **Comments:**
> **username_1**: What is the application in parametrized complexity?  
> **username_2**: 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.  
> **username_0**: In parametrized complexity,  the sunflowers can be used in the kernelization of the hitting set problem.  And thank you for your work!  
> **username_3**: What is the application in cryptography?  
> **username_4**: @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?  
> **username_4**: @VS. possibly the following qualifies as an application in cryptography? https://eprint.iacr.org/2017/015.pdf Caveat emptor: I barely looked at it, and really don't know much about crypto. At least it talks about adversaries, plus it seems to make use of the Sunflower Lemma.  
> **username_5**: @HermannGruber Non-malleable codes are definitely a cryptographic topic.  

---

## 3 answers

### Answer by username_4 on 2020-03-28. Score: 4

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>


---

### Answer by username_6 on 2020-03-28. Score: 4

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](https://eccc.weizmann.ac.il/report/2017/040/).


---

### Answer by username_7 on 2020-03-29. Score: 4

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.


---

