AND operator of many functions
When $f_i$ are given as black boxes, it takes $\Omega(n)$ in the worst case to compute their AND.

The constraints that the question puts on the functions $f_i$, don't really tell anything about $f_i$ and their behavior, maybe except for a very small subset of inputs. For instance, we can assume that over the inputs $x=0,...,n$ each $f_i$ is 1, except for the case where $x=i$. This satisfies all the constraints stated. But if $x&gt;n$ we have no idea how $f_i$ behaves. As a trivial example, it can be that each $f_i$ has some infinite kernel (=values of $x$ that zeroize it), but the union of all the kernels doesn't cover the entire $\mathbb{Z}$. As a block box, it is not clear that you even have a compact way to describe each kernel, and you have no choice but querying the black box.

Even if the kernel of each function is known (and has a compact description), it can be that the most compact description of their union is "the union of the kernel of $f_1$ and $f_2$ and ...", which hints that one must compute each $f_i$ separately to know their AND value. For instance, if $f_1$ is the indicator function of all the prime numbers, and $f_2$ is the indicator of all odd numbers whose binary representation has an equal number of ones and zeros. Probably simpler examples can be found.