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 


6:00pm 

