8:00am 

9:00am 

10:00am 

11:00am 

12:00pm 

1:00pm 

2:00pm 

3:00pm 
[3:00pm]Rajat Mittal (IITK)
 Description:
 Title: Degree of a boolean symmetric function
Speaker: Rajat Mittal (IITK)
DateTime: Thursday, June 27, 2018, 3 PM.
Venue: 216, Dept. of Mathematics, IITB
Abstract: Every boolean function $f:{0,1}^n >{0,1}$ can be represented by a multilinear polynomial of degree less than or equal to $n$. A boolean function is symmetric if it is invariant under any permutation of the input. We consider the natural question, what is minimum possible degree of a symmetric boolean function on
$n$ variables? Gathen et.al. were able to show that any symmetric boolean function will have degree at least $nO(n^{.525})$.
We will give a somewhat simplified proof of the result above and show some other consequences of this proof. We will also discuss possible approaches to tackle this question.

4:00pm 

5:00pm 

