Complexity of computation of ANF-form (Zhegalkin polynomial)

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?

$$\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$$.
• 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?
• 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)$. Apr 27, 2023 at 15:43