Representing boolean function by a polynomial

Question

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?

Answer 1

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.

Answer 2

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$

Background

"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

• Game theory on p.579 [1] with focus on multilinear polynomial extensions with the structure $[0,1]^n$

• Reliability Boolean functions characterised in terms of minimum pathsets and different cuts, some information in p.58 [1], with the structure $[0,1]^n$

• (circuits) Complexity of multi-linear polynomial computing Boolean function

• (fourier analysis) Lower bounds for Polynomials computing the boolean functions

References

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