The Sunflower Lemma and its Application to Circuit Lower Bound

Speaker: 

Time: 

Friday, 20 July 2012, 15:00 to 16:30

Venue: 

  • A212

Organisers: 

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)