Talks - Fall 2017

Four-Bit Majority Circuit

Title

Speaker

Date

Time

Venue

Abstract

Bounds on Degree of Symmetric Boolean Functions

Rajat Mittal

18 Aug, 2017

4pm

KD103

Every boolean function, f:\{0,1\}^n \rightarrow \{0,1\}, can be represented as a polynomial. If the function f is also symmetric, then it can be easily proven that it should have degree at least $n/2$.

We will look at the proof by Gathen and Roche (94), where they prove that the degree is at least n-O(n^(.548)). The talk will be elementary and will be accessible to everyone.

ALL SESSIONS


Contact

Image

Sumanta Ghosh

Head Co-ordinator

Image

Rajendra Kumar

Co-ordinator

Image

Mahesh S R

Co-ordinator