<p>Classes of Boolean functions with unique multilinear presentation contain</p>

<ol>
<li><p>Pseudo-Boolean functions over reals (Theorem 1.34 [1])</p></li>
<li><p>Boolean function over unit cube  $[0,1]^n$ </p></li>
</ol>

<p><em>Background</em></p>

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

<p>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).</p>

<p>and their applications contain</p>

<ul>
<li><p>Game theory on p.579 [1] with focus on multilinear polynomial extensions with the structure $[0,1]^n$</p></li>
<li><p>Reliability Boolean functions characterised in terms of minimum pathsets and different cuts, some information in p.58 [1], with the structure $[0,1]^n$</p></li>
<li><p>(circuits) <a href="https://cstheory.stackexchange.com/questions/32201/complexity-of-multi-linear-polynomial-computing-boolean-function?rq=1">Complexity of multi-linear polynomial computing Boolean function</a></p></li>
<li><p>(fourier analysis) <a href="https://cstheory.stackexchange.com/questions/25291/lower-bounds-for-polynomials-computing-the-boolean-functions">Lower bounds for Polynomials computing the boolean functions</a></p></li>
</ul>

<p><em>References</em></p>

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

CC BY-SA 3.0
2016-02-09T13:48:32.217Z
Yes, obviously. Now, how does that answer the question?
Emil Jeřábek
CC BY-SA 3.0
2016-02-09T13:43:14.120Z
2016-02-09T14:10:34.513Z
2017-04-13T12:32:28.743Z
hhh
<p>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.</p>

<p>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.</p>

CC BY-SA 3.0
2014-10-14T01:05:15.607Z
This is an useful point. What is a good reference for this topic?
Turbo
CC BY-SA 3.0
2014-10-14T01:44:55.617Z
You can take a look at Ryan O'Donnell's recent book, Analysis of Boolean functions.
Yuval Filmus
CC BY-SA 3.0
2014-10-13T17:39:55.660Z
2014-10-14T01:47:08.933Z
2014-10-14T01:47:08.933Z
Yuval Filmus
<p>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?</p>

CC BY-SA 3.0
2014-10-13T07:36:48.810Z
Related: http://cstheory.stackexchange.com/questions/25291/lower-bounds-for-polynomials-computing-the-boolean-functions
Andrej Bauer
CC BY-SA 3.0
2014-10-13T22:10:48.263Z
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.
usul
<boolean-functions>
Representing boolean function by a polynomial
Turbo
# Representing boolean function by a polynomial

(Asked by: username_0 on 2014-10-13)

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?

**Tags:** boolean-functions
> **Comments:**
> **username_1**: Related: http://cstheory.stackexchange.com/questions/25291/lower-bounds-for-polynomials-computing-the-boolean-functions  
> **username_2**: 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.  

---

## 2 answers

### Answer by username_5 on 2014-10-13. Score: 10 | Accepted answer

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.

> **Comments:**
> **username_0**: This is an useful point. What is a good reference for this topic?  
> **username_5**: You can take a look at Ryan O'Donnell's recent book, Analysis of Boolean functions.  

---

### Answer by username_3 on 2016-02-09. Score: 0

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](https://cstheory.stackexchange.com/questions/32201/complexity-of-multi-linear-polynomial-computing-boolean-function?rq=1)
* (fourier analysis) [Lower bounds for Polynomials computing the boolean functions](https://cstheory.stackexchange.com/questions/25291/lower-bounds-for-polynomials-computing-the-boolean-functions)

*References*

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

> **Comments:**
> **username_4**: Yes, obviously. Now, how does that answer the question?  

---

