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.