Thu, June 28, 2018
Public Access Category: All |
||||||||||||||||||||||
|
- Time:
- 3:00pm
- Location:
- Room No. 216, Department of Mathematics
- 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.