4
$\begingroup$

This is a reference request. I'm interested in the compositional construction of small boolean circuits for vector-valued boolean functions $\phi : \mathbb{B}^m \rightarrow \mathbb{B}^n$ for $n > 1$, assuming we can construct small boolean circuits for boolean functions $\phi : \mathbb{B}^m \rightarrow \mathbb{B}^1$. How much does that help? It's a natural question. Surely this must have been investigated? If so, what are the main results, and under what name has is this studied?


Let's make this more precise. We use $C$ to range over boolean circuits (the details, like what is the basis for gates, whether NAND, XOR, AND/NOT, etc, does not matter, I'd be grateful for reference requests for any basis). Write $eval(C)$ for the boolean function $\mathbb{B}^m \rightarrow \mathbb{B}^n$ that $C$ induces. If $\phi$ is a function $\mathbb{B}^m \rightarrow \mathbb{B}^n$, and $C$ a circuit, we write

$$ \phi \cong C $$

if $eval(C)$ is the same function as $\phi$. We write $size(C)$ for the chosen notion of circuit size (again details don't matter, whether number of edges, number of nodes etc). Let $size_{\min}(\phi)$ be the size of minimal circuits for $\phi$, in other words:

$$ \min \{ size(C)\ |\ C\ \text{circuit with}\ eval(C) \cong \phi\} $$

We say $C$ is an $\epsilon$-optimal approximation of $\phi$ if

  • $\phi \cong C$
  • $| size_{\min}(\phi) - size(C) | \leq \epsilon$

Let's now assume we have an oracle for $\epsilon$-optimal approximations of boolean functions $\mathbb{B}^m \rightarrow \mathbb{B}$. Now assume given a vector valued boolean function

$$ \phi : \mathbb{B}^m \rightarrow \mathbb{B}^n $$

We write $\phi_1 : \mathbb{B}^m \rightarrow \mathbb{B}$, ..., $\phi_n : \mathbb{B}^m \rightarrow \mathbb{B}$ for the $n$ components of $\phi$, i.e.

$$ \phi(\vec{b}) = (\phi_1(\vec{b}), ..., \phi_n(\vec{b})) $$

How much does having oracle access to $\epsilon$-optimal approximations of the $\phi_i$, help us in the construction of $\epsilon$-optimal approximations of $\phi$ (or, more generally, $\delta$-optimal approximations of $\phi$)?

$\endgroup$
2
  • $\begingroup$ Do you really mean to measure $\epsilon$-optimal using additive error rather than relative (multiplicative) error? $\endgroup$
    – D.W.
    May 13 at 7:21
  • $\begingroup$ @D.W. My use-case is additive, but I'd also be very interested in multiplicative errors. That might be informative, and I should definitely write about multiplicative in the related work section. Basically any result about the compositional construction of vector valued boolean circuits from from boolean functions with single bit output is of interest to me. $\endgroup$ May 13 at 7:54

1 Answer 1

1
$\begingroup$

I doubt it. At least, not in all cases.

Suppose that you are working in a circuit model where every function $\mathbb{B}^k\to\mathbb{B}$ can be represented by a circuit with $\le 2^k+1$ gates, say by representing it in DNF form, and that most such functions require a circuit of size $\ge c \cdot 2^k$ for some constant $c>0$.

Consider a function of the form $\phi = h \circ g \circ f$ where $f:\mathbb{B}^n \to \mathbb{B}^k$ is some efficiently computable function (e.g., a cryptographic hash function; a random linear map) with a small circuit, $g:\mathbb{B}^k \to \mathbb{B}^k$ is a function whose minimal circuit has size approximately $2^k$ (e.g., let $\pi:\mathbb{B}^k \to \mathbb{B}^k$ be an unkeyed bijective function that behaves like a random permutation, see e.g https://crypto.stackexchange.com/q/33831/351, and let $g(x)=\pi^r(x)$ where $r$ is chosen to achieve the desired minimal circuit size for $g$), and $h:\mathbb{B}^k \to \mathbb{B}^m$ is some efficiently computable function (e.g., a cryptographic hash function; a random linear map) with a small circuit.

Then $\phi$ has a circuit of size $2^k +$ a little (to account for the size of the circuits of $f,h$, which are small compared to $2^k$).

However, for each $i$, we expect the smallest circuit for $\phi_i$ will be obtained by treating $(h \circ g)_i$ as a generic function $\mathbb{B}^k \to \mathbb{B}$, whose minimal circuit has size between $c \cdot 2^k$ and $2^k$ by using a generic construction (e.g., representing it in DNF form), and then composing with a circuit for $f$. As such, I don't expect the minimal circuit of $\phi_i$ to contain much useful information about the minimal circuit of $\phi$. I expect that just gluing together the minimal circuit for all the $\phi_i$'s together will give a circuit for $\phi$ of size between $cm \cdot 2^k$ and $m \cdot 2^k$ (roughly), whereas the minimal circuit for $\phi$ has size $2^k$ (roughly), leaving a big gap between what you obtain from your oracles for each $\phi_i$ vs the desired minimal circuit for $\phi$. $\epsilon$-approximation doesn't seem to help.

This is not a proof. This is just a "plausibility argument" designed to give some intuition about what I expect the "right answer" might be.

$\endgroup$
1
  • $\begingroup$ Thanks. This aligns with my experiments of brute-forcing a large number of tiny circuits: there are cases where the components don't help. However, my tiny and ad-hoc experiments also seem to show that they often do help. This might be an effect of just looking at tiny tiny circuits (brute-force doesn't get far). $\endgroup$ May 14 at 15:22

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.