Login 
Thursday, June 28, 2018
Public Access


Category:
Category: All

28
June 2018
Mon Tue Wed Thu Fri Sat Sun
        1 2 3
4 5 6 7 8 9 10
11 12 13 14 15 16 17
18 19 20 21 22 23 24
25 26 27 28 29 30  
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) Date-Time: 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 multi-linear 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 $n-O(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