10
$\begingroup$

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?

Improve this question
$\endgroup$
2
  • 2
    $\begingroup$ Related: cstheory.stackexchange.com/questions/25291/… $\endgroup$
    – Andrej Bauer
    Oct 13 '14 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 '14 at 22:10
10
$\begingroup$

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.

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

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

References

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

Improve this answer
$\endgroup$
1
  • 1
    $\begingroup$ Yes, obviously. Now, how does that answer the question? $\endgroup$
    – Emil Jeřábek
    Feb 9 '16 at 13:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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