<p><span class="math-container">$\def\ff{\mathbb F_2}\def\sset{\subseteq}$</span>Given the truth-table <span class="math-container">$\langle f(a):a\in\ff^k\rangle$</span> of a function <span class="math-container">$f\colon\ff^k\to\ff$</span>, its multilinear expansion can be explicitly computed by
<span class="math-container">$$\begin{align*}f(x)&amp;=\sum_{a\in\ff^k}f(a)\prod_{i\in[k]}(x_i+a_i+1)\\
&amp;=\sum_{a\in\ff^k}f(a)\sum_{I\sset[k]}\prod_{i\in I}x_i\prod_{i\notin I}(a_i+1)\\
&amp;=\sum_{a\in\ff^k}f(a)\sum_{a^{-1}(1)\sset I\sset[k]}\prod_{i\in I}x_i\\
&amp;=\sum_{I\sset[k]}\prod_{i\in I}x_i\underbrace{\sum_{\substack{a\in\ff^k\\a^{-1}(1)\sset I}}f(a)}_{f_I},
\end{align*}$$</span>
where <span class="math-container">$a^{-1}(1)=\{i\in[k]:a_i=1\}$</span>. That is, each coefficient <span class="math-container">$f_I$</span> is a sum (modulo <span class="math-container">$2$</span>) of certain entries of the truth table; thus, we can compute <span class="math-container">$\langle f_I:I\sset[k]\rangle$</span> using a uniform <span class="math-container">$\mathrm{AC}^0[2]$</span> circuit, and then for a given <span class="math-container">$d$</span>,
<span class="math-container">$$\operatorname{deg}(f)\ge d\iff\bigvee_{|I|\ge d}f_I$$</span>
is also computable in uniform <span class="math-container">$\mathrm{AC}^0[2]$</span>.</p>
<p>On the other hand, the problem is <span class="math-container">$\mathrm{AC}^0[2]$</span>-complete: by the expansion above, <span class="math-container">$f_{[k]}$</span> is the parity of the whole truth table (considered as a string); observe that <span class="math-container">$f_{[k]}=1\iff\operatorname{deg}(f)\ge k$</span>.</p>

CC BY-SA 4.0
2023-04-27T15:36:18.163Z
It seems like if $d$ is sufficiently large (so that the OR only ranges over a polylog number of different subsets) then the problem is in $CC^0[2p]$ for any prime $p \neq 2$ as well, right?
Jake
CC BY-SA 4.0
2023-04-27T15:43:30.637Z
Yes, I believe so, but this is applicable only to a few values of $d$. I suppose polylog means polylogarithmic in the size of the input, which is $2^k$, i.e., polynomial in $k$. Even so, the number of the sets is roughly $k^{k-d}$, hence it is polynomial in $k$ only if $d=k-O(1)$.
Emil Jeřábek
CC BY-SA 4.0
2023-04-26T19:26:35.287Z
2023-04-26T19:26:35.287Z
Emil Jeřábek
<p>Let <span class="math-container">$f: \mathbb{F}_2^n \to \mathbb{F}_2$</span> be a boolean function.
Consider <span class="math-container">$f$</span> as a multilinear polynomial over <span class="math-container">$\mathbb{F}_2$</span> (algebraic normal form or Zhegalkin polynomial).</p>
<p>How hard is to define the degree of <span class="math-container">$f$</span> if <span class="math-container">$f$</span> is given as truth-table?</p>
<p>It is  easy to see that this can be done in polynomial time, but does the corresponding decision problem is P-complete?</p>

<complexity-classes><polynomials>
Complexity of computation of ANF-form (Zhegalkin polynomial)
Alexey Milovanov
# Complexity of computation of ANF-form (Zhegalkin polynomial)

(Asked by: username_0 on 2023-04-25)

Let $f: \mathbb{F}\_2^n \to \mathbb{F}\_2$ be a boolean function.
Consider $f$ as a multilinear polynomial over $\mathbb{F}\_2$ (algebraic normal form or Zhegalkin polynomial).

How hard is to define the degree of $f$ if $f$ is given as truth-table?

It is easy to see that this can be done in polynomial time, but does the corresponding decision problem is P-complete?

**Tags:** complexity-classes, polynomials


---

## 1 answers

### Answer by username_1 on 2023-04-26. Score: 2 | Accepted answer

$\def\ff{\mathbb F\_2}\def\sset{\subseteq}$Given the truth-table $\langle f(a):a\in\ff^k\rangle$ of a function $f\colon\ff^k\to\ff$, its multilinear expansion can be explicitly computed by
$$\begin{align\*}f(x)&=\sum\_{a\in\ff^k}f(a)\prod\_{i\in[k]}(x\_i+a\_i+1)\\
&=\sum\_{a\in\ff^k}f(a)\sum\_{I\sset[k]}\prod\_{i\in I}x\_i\prod\_{i\notin I}(a\_i+1)\\
&=\sum\_{a\in\ff^k}f(a)\sum\_{a^{-1}(1)\sset I\sset[k]}\prod\_{i\in I}x\_i\\
&=\sum\_{I\sset[k]}\prod\_{i\in I}x\_i\underbrace{\sum\_{\substack{a\in\ff^k\\a^{-1}(1)\sset I}}f(a)}\_{f\_I},
\end{align\*}$$
where $a^{-1}(1)=\{i\in[k]:a\_i=1\}$. That is, each coefficient $f\_I$ is a sum (modulo $2$) of certain entries of the truth table; thus, we can compute $\langle f\_I:I\sset[k]\rangle$ using a uniform $\mathrm{AC}^0[2]$ circuit, and then for a given $d$,
$$\operatorname{deg}(f)\ge d\iff\bigvee\_{|I|\ge d}f\_I$$
is also computable in uniform $\mathrm{AC}^0[2]$.

On the other hand, the problem is $\mathrm{AC}^0[2]$-complete: by the expansion above, $f\_{[k]}$ is the parity of the whole truth table (considered as a string); observe that $f\_{[k]}=1\iff\operatorname{deg}(f)\ge k$.

> **Comments:**
> **username_2**: It seems like if $d$ is sufficiently large (so that the OR only ranges over a polylog number of different subsets) then the problem is in $CC^0[2p]$ for any prime $p \neq 2$ as well, right?  
> **username_1**: Yes, I believe so, but this is applicable only to a few values of $d$. I suppose polylog means polylogarithmic in the size of the input, which is $2^k$, i.e., polynomial in $k$. Even so, the number of the sets is roughly $k^{k-d}$, hence it is polynomial in $k$ only if $d=k-O(1)$.  

---

