BEGIN:VCALENDAR
PRODID:-//eluceo/ical//2.0/EN
VERSION:2.0
CALSCALE:GREGORIAN
BEGIN:VEVENT
UID:www.tcs.tifr.res.in/event/292
DTSTAMP:20230914T125918Z
SUMMARY:The Sunflower Lemma and its Application to Circuit Lower Bound
DESCRIPTION:Speaker: Deepesh Data\n\nAbstract: \nSunflowers are highly reg
ular configurations in extremal set theory. The sunflower lemma discovered
by Erdos and Rado in 1960 asserts that in a sufficiently large uniform fa
mily\, some highly regular configuration called "Sunflower" must occur\, r
egardless of the size of the universe. In this talk we'll consider this re
sult as well as one of its modification (called Flower lemma) and its appl
ication. \nThe sunflower lemma and its modifications have many applicatio
ns in computational complexity theory. We'll only prove lower bound of a s
pecial 3-depth formula computing an s-threshold function (An s-threshold f
unction is a monotone Boolean function which outputs 1 iff at least s of i
ts inputs are 1).\nReference : Chapter 6\, Extremal Combinatorics with app
lications in computer science\, 2nd edition\, Springer (Author : Stasys Ju
kna)\n
URL:https://www.tcs.tifr.res.in/web/events/292
DTSTART;TZID=Asia/Kolkata:20120720T150000
DTEND;TZID=Asia/Kolkata:20120720T163000
LOCATION:A212
END:VEVENT
END:VCALENDAR