2
$\begingroup$

Given a Boolean function $f:\{0,1\}^n\rightarrow\{0,1\}$, there is a real multivariate multilinear polynomial that is associated with in through interpolation.

Example: $AND(x_1,x_2,\dots,x_{n-1},x_n)$ is associated with $\prod_{i=1}^nx_i$.

Degree of Boolean function is least possible total degree of real multivariate multilinear polynomial associated with it.

How many degree $k$ Boolean functions are there with $n$ variables out of total $2^{2^n}$ functions?

Is there an inductive procedure?

Improve this question
$\endgroup$
8
  • $\begingroup$ How many degree $\le k$ multilinear monomials in $n$ variables are there? This is trivial combinatorics. $\endgroup$
    – Emil Jeřábek
    Commented Jan 13, 2015 at 12:31
  • 1
    $\begingroup$ Or are you talking about a different field than $\mathbb F_2$, by any chance? Then you need to make that explicit in the question. $\endgroup$
    – Emil Jeřábek
    Commented Jan 13, 2015 at 13:31
  • $\begingroup$ I am talking about reals. $\endgroup$
    – Turbo
    Commented Jan 13, 2015 at 18:59
  • $\begingroup$ This is elementary linear algebra. Why are you asking this on a research mathematics site? $\endgroup$
    – S. Carnahan ♦
    Commented Jan 14, 2015 at 1:50
  • $\begingroup$ I am getting not much help here math.stackexchange.com/questions/1103587/…? $\endgroup$
    – Turbo
    Commented Jan 14, 2015 at 8:11

0

Reset to default