Cheap and Secure Web Hosting Provider : See Now

Boolean function and real degree

, , No Comments
Problem Detail: 

Let $f$ be a boolean function with minimum degree real polynomial representing it be of degree $d$.

Is there a relation between number of zeros $f$ or $1-f$ and degree $d$?

Asked By : Turbo
Answered By : Yuval Filmus

Exercise 12 (online version) in §1 of Ryan O'Donnell's Analysis of Boolean functions shows that all Fourier coefficients of a degree $d$ function are integer multiples of $2^{-d}$. In particular, the number of zeroes of $f$ is an integer multiple of $2^{n-d}$.

Moreover, for every integer $k \in \{0,\ldots,2^d\}$ there is a degree $d$ Boolean function having exactly $k2^{n-d}$ zeroes. This easily follows from the fact that a function on $d$ variables has degree at most $d$.

Best Answer from StackOverflow

Question Source :

3200 people like this

 Download Related Notes/Documents


Post a Comment

Let us know your responses and feedback