6
$\begingroup$

Let $f : \mathbb{F}_2^n \to \mathbb{F}_2$ be a Boolean function in $n$ variables. The zeta transform of $f$ is the Boolean function $\zeta_f : \mathbb{F}_2^n \to \mathbb{F}_2$ defined by $$\zeta_f(y) := \sum_{x \leq y} f(x) \label{1}\tag{⋆} $$ for every $y \in \mathbb{F}_2^n$. Here, for $x=(x_1, \dots, x_n)$ and $y=(y_1, \dots, y_n)$ in $\mathbb{F}_2^n$, the notation $x \leq y$ means that $x_i \leq y_i$ for $i=1,\dots,n$.

I am interested in the space and time complexities of algorithms to compute the values $(\zeta_f(y))_{y \in \mathbb{F}_2^n}$ given $f$ as a black box.

The trivial algorithm that simply compute $\zeta_f(y)$ using \eqref{1} has time complexity $O(3^n)$$^{\text{[note 1]}}$ and space complexity $O(1)$.$^{\text{[note 2]}}$

The so-called Yate's algorithm has time complexity $O(n 2^n)$$^{\text{[note 3]}}$ and space complexity $O(2^n)$.

Is there an algorithm having smaller time complexity than the trivial algorithm and also smaller space complexity than the Yate's algorithm? Say $O(2.5^n)$ and $O(1.5^n)$, for example.

Thanks for any help.

Note 1: For each $y \in \mathbb{F}_2$ of Hamming weight $w$, to compute $\zeta_f(y)$ using \eqref{1} we have to sum $2^w$ values, so the time complexity is of the order $\sum_{w \leq n} 2^w \binom{n}{w} = 3^n$.

Note 2: Assuming that each value $\zeta_f(y)$ is printed immediately after its computation, and so it requires no memory to be stored.

Note 3: The time complexity cannot be less than $O(2^n)$, since there are $2^n$ values $(\zeta_f(y))_{y \in \mathbb{F}^n_2}$ to be computed.

$\endgroup$
2
  • $\begingroup$ There is a fast zeta transform hidden in the second part of the paper arxiv.org/pdf/0905.1340.pdf as a tool to compute fast Fourier transforms of rook monoids. I don't know the details $\endgroup$ Mar 13, 2021 at 16:22
  • $\begingroup$ If you focus on time complexity only this paper arxiv.org/abs/1304.1122 seems to state a lower bound to it of O(n2n). This transform is also referred to as the Mobius transform in the literature. $\endgroup$
    – kodlu
    Mar 14, 2021 at 0:43

0

Your Answer

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