Evaluate boolean circuit on batch of similar inputs

Question

Suppose I have a boolean circuit $C$ that computes some function $f:\{0,1\}^n \to \{0,1\}$. Assume the circuit is composed of AND, OR, and NOT gates with fan-in and fan-out at most 2.

Let $x \in \{0,1\}^n$ be a given input. Given $C$ and $x$, I want to evaluate $C$ on the $n$ inputs that differ from $x$ in a single bit position, i.e., to compute the $n$ values $C(x^1),C(x^2),\dots,C(x^n)$ where $x^i$ is the same as $x$ except that its $i$th bit is flipped.

Is there a way to do this that is more efficient that independently evaluating $C$ $n$ times on the $n$ different inputs?

Assume $C$ contains $m$ gates. Then independently evaluating $C$ on all $n$ inputs will take $O(mn)$ time. Is there a way to compute $C(x^1),C(x^2),\dots,C(x^n)$ in $o(mn)$ time?

---

Optional context: If we had an arithmetic circuit (whose gates are multiplication, addition, and negation) over $\mathbb{R}$, then it would be possible to compute the $n$ directional derivatives ${\partial f \over \partial x_i}(x)$ in $O(m)$ time. Basically, we could use standard methods for computation of the gradient (back-propagation / chain rule), in $O(m)$ time. That works because the corresponding function is continuous and differentiable. I'm wondering whether something similar can be done for boolean circuits. Boolean circuits aren't continuous and differentiable, so you can't do the same trick, but maybe there is some other clever technique one can use? Maybe some kind of Fourier trick, or something?

(Variant question: if we have boolean gates with unbounded fan-in and bounded fan-out, can you do do asymptotically better than evaluating $C$ $n$ times?)

Answer 1

I'd consider it unlikely that such a trick is easy to find and/or will give you significant gains, as it would give nontrivial satisfiability algorithms. Here's how:

First of all, while ostensibly easier, your problem can actually solve the more general problem of, given a circuit $C$ and $N$ inputs $x_0, \ldots, x_{N-1}$, evaluate $C$ at all the inputs faster than $\tilde{O}(N\cdot|C|)$ time. The reason is that we can tweak $C$ into a circuit $C'$ of size $|C| + \tilde{O}(Nn)$ which, on input $0^i10^{N-1-i}$, outputs $C(x_{i})$. Basically, we just make a little lookup table that sends $0^i10^{N-1-i}$ to $x_i$, and wire it into $C$.

Nontrivial algorithms for batch evaluation of boolean-circuits can then be used to make fast satisfiability algorithms. Here's an example in the simple case where we suppose we have an algorithm doing evaluation in time $\tilde{O}(|C|^{2-\epsilon} + (N\cdot|C|)^{1-\epsilon/2} + N^{2-\epsilon})$ for any constant $\epsilon > 0$. On input a circuit $C$, we can decide satisfiability by expanding $C$ into a circuit $C'$ of size $2^{n/2}\cdot |C|$ which is just the OR over all possible choices of the first $n/2$ inputs to $C$ (leaving the other inputs free). We then batch-evaluate $C'$ on all of its $2^{n/2}$ inputs. The end result is that we find a satisfying assignment to $C'$ iff $C$ is satisfiable. The running time is $\tilde{O}(2^{(n/2)(2-\epsilon)}\cdot |C|^{2-\epsilon}) = \tilde{O}(2^{n(1-\epsilon/2)}\cdot \textrm{poly}(|C|))$.