# Applications of sunflower lemma in theoretical computer science

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

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

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?

• What is the application in parametrized complexity? – 1.. Mar 24 at 6:17
• 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 Mar 24 at 9:35
• In parametrized complexity, the sunflowers can be used in the kernelization of the hitting set problem. And thank you for your work! – Bubble Mar 24 at 13:56
• @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 Mar 29 at 20:07
• @HermannGruber Non-malleable codes are definitely a cryptographic topic. – Mark Mar 29 at 22:48

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