2
$\begingroup$

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?

$\endgroup$
0

1 Answer 1

2
$\begingroup$

$\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$.

$\endgroup$
2
  • $\begingroup$ 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? $\endgroup$
    – Jake
    Apr 27, 2023 at 15:36
  • 1
    $\begingroup$ 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)$. $\endgroup$ Apr 27, 2023 at 15:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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