Tata Institute of Fundamental Research
The Sunflower Lemma and its Application to Circuit Lower Bound
Student Seminar
Speaker:
Deepesh Data
Organiser:
Sarat Babu Moka
Date:
Friday, 20 Jul 2012, 15:00 to 16:30
Venue:
A212
(Scan to add to calendar)
Abstract:
Sunflowers are highly regular configurations in extremal set theory. The sunflower lemma discovered by Erdos and Rado in 1960 asserts that in a sufficiently large uniform family, some highly regular configuration called "Sunflower" must occur, regardless of the size of the universe. In this talk we'll consider this result as well as one of its modification (called Flower lemma) and its application.
The sunflower lemma and its modifications have many applications in computational complexity theory. We'll only prove lower bound of a special 3-depth formula computing an s-threshold function (An s-threshold function is a monotone Boolean function which outputs 1 iff at least s of its inputs are 1).
Reference : Chapter 6, Extremal Combinatorics with applications in computer science, 2nd edition, Springer (Author : Stasys Jukna)
| Speaker: | Deepesh Data |
| Organiser: | Sarat Babu Moka |
| Date: | Friday, 20 Jul 2012, 15:00 to 16:30 |
| Venue: | A212 |
(Scan to add to calendar)
Abstract:
Sunflowers are highly regular configurations in extremal set theory. The sunflower lemma discovered by Erdos and Rado in 1960 asserts that in a sufficiently large uniform family, some highly regular configuration called "Sunflower" must occur, regardless of the size of the universe. In this talk we'll consider this result as well as one of its modification (called Flower lemma) and its application.
The sunflower lemma and its modifications have many applications in computational complexity theory. We'll only prove lower bound of a special 3-depth formula computing an s-threshold function (An s-threshold function is a monotone Boolean function which outputs 1 iff at least s of its inputs are 1).
Reference : Chapter 6, Extremal Combinatorics with applications in computer science, 2nd edition, Springer (Author : Stasys Jukna)
The sunflower lemma and its modifications have many applications in computational complexity theory. We'll only prove lower bound of a special 3-depth formula computing an s-threshold function (An s-threshold function is a monotone Boolean function which outputs 1 iff at least s of its inputs are 1).
Reference : Chapter 6, Extremal Combinatorics with applications in computer science, 2nd edition, Springer (Author : Stasys Jukna)