Supposing we have a boolean function from $f:\{0,1\}^n\rightarrow\{0,1\}$. It is clear that a real multivariate polynomial $p(x)$ such that $f(x)=p(x)$ on $x\in\{0,1\}^n$ can be multilinear. What are some interesting classes of boolean functions for which the minimal degree of $p(x)$ is known? Do we have concrete examples?

  • 2
    $\begingroup$ Related: cstheory.stackexchange.com/questions/25291/… $\endgroup$ Oct 13, 2014 at 7:36
  • 1
    $\begingroup$ If you're not familiar with it, closely related is lots of work on "approximate degree", which asks, what is the minimal degree of a polynomial that "approximates" $f$? I don't know enough to give specific references but others would. $\endgroup$
    – usul
    Oct 13, 2014 at 22:10

2 Answers 2


Any function which has non-zero correlation with parity has degree $n$. That is, if $$\sum_{x \in \{0,1\}^n} (-1)^{\sum_i x_i}f(x) \neq 0$$ then the unique multilinear expansion of $f$ contains the monomial $x_1\cdots x_n$. Indeed, since $(-1)^{x_i} = \frac{1-x_i}{2}$, the Fourier expansion of $f$ (expressed in terms of products of $\frac{1-x_i}{2}$) will contain the term $\prod_i \frac{1-x_i}{2}$, and the corresponding monomial $\prod_i x_i$ doesn't appear in any other term.

Nisan and Szegedy proved that functions of degree $d$ depend on at most $d2^d$ variables. For $d = 1$ we can be more exact: the function must depend on at most one coordinate.

  • $\begingroup$ This is an useful point. What is a good reference for this topic? $\endgroup$
    – Turbo
    Oct 14, 2014 at 1:05
  • 3
    $\begingroup$ You can take a look at Ryan O'Donnell's recent book, Analysis of Boolean functions. $\endgroup$ Oct 14, 2014 at 1:44

Classes of Boolean functions with unique multilinear presentation contain

  1. Pseudo-Boolean functions over reals (Theorem 1.34 [1])

  2. Boolean function over unit cube $[0,1]^n$


"Every Boolean function can be represented by a disjunctive normal form and by a conjuctive normal form." (Theorem 1.4 (p.16 [1])

so every disjunctive normal form (DNF) of the form $\vee (\wedge {x} \wedge \bar{x} )$ can be written as $\vee (\prod x \prod (1-x))$ and $\sum c \prod x$ and further definitions on the page 18 of the book such as subscripts. You can represent every Boolean function $F$ on $\mathcal B^n$ in terms of powerset $\mathcal P(N)$ and direct sum $\oplus$ such that $f(x_1,\ldots,x_n)=\oplus_{A\in\mathcal P(N)} c(A)\prod_{i\in A} x_i$ (THM1.33).

and their applications contain


[1] Boolean Functions Theory, Algorithms, and Applications (Yves Crama, Peter L. Hammer, 2011)

  • 1
    $\begingroup$ Yes, obviously. Now, how does that answer the question? $\endgroup$ Feb 9, 2016 at 13:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.