Speaker: |
Deepesh Data |

Organiser: |
Sarat Babu Moka |

Date: |
Friday, 20 Jul 2012, 15:00 to 16:30 |

Venue: |
A212 |

(Scan to add to calendar)

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)