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?
Asked
Active
Viewed 1,962 times
11
-
2Related: http://cstheory.stackexchange.com/questions/25291/lower-bounds-for-polynomials-computing-the-boolean-functions – Andrej Bauer Oct 13 '14 at 07:36
-
1If 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. – usul Oct 13 '14 at 22:10
2 Answers
10
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.
Yuval Filmus
- 14,445
- 1
- 48
- 92
-
-
3You can take a look at Ryan O'Donnell's recent book, Analysis of Boolean functions. – Yuval Filmus Oct 14 '14 at 01:44
0
Classes of Boolean functions with unique multilinear presentation contain
Pseudo-Boolean functions over reals (Theorem 1.34 [1])
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)
