<p>I doubt it.  At least, not in all cases.</p>
<p>Suppose that you are working in a circuit model where every function <span class="math-container">$\mathbb{B}^k\to\mathbb{B}$</span> can be represented by a circuit with <span class="math-container">$\le 2^k+1$</span> gates, say by representing it in DNF form, and that most such functions require a circuit of size <span class="math-container">$\ge c \cdot 2^k$</span> for some constant <span class="math-container">$c&gt;0$</span>.</p>
<p>Consider a function of the form <span class="math-container">$\phi = h \circ g \circ f$</span> where <span class="math-container">$f:\mathbb{B}^n \to \mathbb{B}^k$</span> is some efficiently computable function (e.g., a cryptographic hash function; a random linear map) with a small circuit, <span class="math-container">$g:\mathbb{B}^k \to \mathbb{B}^k$</span> is a function whose minimal circuit has size approximately <span class="math-container">$2^k$</span> (e.g., let <span class="math-container">$\pi:\mathbb{B}^k \to \mathbb{B}^k$</span> be an unkeyed bijective function that behaves like a random permutation, see e.g <a href="https://crypto.stackexchange.com/q/33831/351">https://crypto.stackexchange.com/q/33831/351</a>, and let <span class="math-container">$g(x)=\pi^r(x)$</span> where <span class="math-container">$r$</span> is chosen to achieve the desired minimal circuit size for <span class="math-container">$g$</span>), and <span class="math-container">$h:\mathbb{B}^k \to \mathbb{B}^m$</span> is some efficiently computable function (e.g., a cryptographic hash function; a random linear map) with a small circuit.</p>
<p>Then <span class="math-container">$\phi$</span> has a circuit of size <span class="math-container">$2^k +$</span> a little (to account for the size of the circuits of <span class="math-container">$f,h$</span>, which are small compared to <span class="math-container">$2^k$</span>).</p>
<p>However, for each <span class="math-container">$i$</span>, we expect the smallest circuit for <span class="math-container">$\phi_i$</span> will be obtained by treating <span class="math-container">$(h \circ g)_i$</span> as a generic function <span class="math-container">$\mathbb{B}^k \to \mathbb{B}$</span>, whose minimal circuit has size between <span class="math-container">$c \cdot 2^k$</span> and <span class="math-container">$2^k$</span> by using a generic construction (e.g., representing it in DNF form), and then composing with a circuit for <span class="math-container">$f$</span>.  As such, I don't expect the minimal circuit of <span class="math-container">$\phi_i$</span> to contain much useful information about the minimal circuit of <span class="math-container">$\phi$</span>.  I expect that just gluing together the minimal circuit for all the <span class="math-container">$\phi_i$</span>'s together will give a circuit for <span class="math-container">$\phi$</span> of size between <span class="math-container">$cm \cdot 2^k$</span> and <span class="math-container">$m \cdot 2^k$</span> (roughly), whereas the minimal circuit for <span class="math-container">$\phi$</span> has size <span class="math-container">$2^k$</span> (roughly), leaving a big gap between what you obtain from your oracles for each <span class="math-container">$\phi_i$</span> vs the desired minimal circuit for <span class="math-container">$\phi$</span>.  <span class="math-container">$\epsilon$</span>-approximation doesn't seem to help.</p>
<p>This is not a proof.  This is just a &quot;plausibility argument&quot; designed to give some intuition about what I expect the &quot;right answer&quot; might be.</p>

CC BY-SA 4.0
2024-05-14T15:22:25.467Z
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).
Martin Berger
CC BY-SA 4.0
2024-05-13T21:36:23.900Z
2024-05-13T21:36:23.900Z
D.W.
<p><strong>This is a reference request</strong>.    I'm
interested in the compositional construction of small boolean circuits
for vector-valued boolean functions <span class="math-container">$\phi : \mathbb{B}^m \rightarrow
\mathbb{B}^n$</span> for <span class="math-container">$n &gt; 1$</span>, assuming we can construct small boolean
circuits for boolean functions <span class="math-container">$\phi : \mathbb{B}^m \rightarrow
\mathbb{B}^1$</span>. 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?</p>
<hr />
<p>Let's make this more precise.  We use <span class="math-container">$C$</span> 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 <span class="math-container">$eval(C)$</span> for the boolean function <span class="math-container">$\mathbb{B}^m \rightarrow \mathbb{B}^n$</span> that <span class="math-container">$C$</span> induces.  If <span class="math-container">$\phi$</span> is a function <span class="math-container">$\mathbb{B}^m \rightarrow \mathbb{B}^n$</span>, and <span class="math-container">$C$</span> a
circuit, we write</p>
<p><span class="math-container">$$
   \phi \cong C
$$</span></p>
<p>if <span class="math-container">$eval(C)$</span> is the same function as <span class="math-container">$\phi$</span>.  We write <span class="math-container">$size(C)$</span> for
the chosen notion of circuit size (again details don't matter, whether
number of edges, number of nodes etc).  Let <span class="math-container">$size_{\min}(\phi)$</span> be the
size of minimal circuits for <span class="math-container">$\phi$</span>, in other words:</p>
<p><span class="math-container">$$
   \min \{ size(C)\ |\  C\ \text{circuit with}\ eval(C) \cong \phi\}
$$</span></p>
<p>We say <span class="math-container">$C$</span> is an <span class="math-container">$\epsilon$</span>-optimal approximation of <span class="math-container">$\phi$</span> if</p></p>
<ul>
<li><span class="math-container">$\phi \cong C$</span></li>
<li><span class="math-container">$| size_{\min}(\phi) - size(C) | \leq \epsilon$</span></li>
</ul>
<p>Let's now assume we have an oracle for <span class="math-container">$\epsilon$</span>-optimal
approximations of boolean functions <span class="math-container">$\mathbb{B}^m \rightarrow
\mathbb{B}$</span>. Now assume given a vector valued boolean function</p>
<p><span class="math-container">$$
   \phi : \mathbb{B}^m \rightarrow \mathbb{B}^n
$$</span></p>
<p>We write <span class="math-container">$\phi_1 : \mathbb{B}^m \rightarrow \mathbb{B}$</span>, ..., <span class="math-container">$\phi_n
: \mathbb{B}^m \rightarrow \mathbb{B}$</span> for the <span class="math-container">$n$</span> components of
<span class="math-container">$\phi$</span>, i.e.</p>
<p><span class="math-container">$$
   \phi(\vec{b}) = (\phi_1(\vec{b}), ..., \phi_n(\vec{b}))
$$</span></p>
<p>How much does having oracle access to <span class="math-container">$\epsilon$</span>-optimal
approximations of the <span class="math-container">$\phi_i$</span>, help us in the construction of
<span class="math-container">$\epsilon$</span>-optimal approximations of <span class="math-container">$\phi$</span> (or, more generally,
<span class="math-container">$\delta$</span>-optimal approximations of <span class="math-container">$\phi$</span>)?</p>

CC BY-SA 4.0
2024-05-13T07:21:32.780Z
Do you really mean to measure $\epsilon$-optimal using additive error rather than relative (multiplicative) error?
D.W.
CC BY-SA 4.0
2024-05-13T07:54:35.913Z
@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.
Martin Berger
<cc.complexity-theory><reference-request><circuit-complexity><boolean-functions><circuits>
Constructing vector valued boolean circuits from boolean circuits
Martin Berger
# Constructing vector valued boolean circuits from boolean circuits

(Asked by: username_0 on 2024-05-12)

**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$)?

**Tags:** cc.complexity-theory, reference-request, circuit-complexity, boolean-functions, circuits
> **Comments:**
> **username_1**: Do you really mean to measure $\epsilon$-optimal using additive error rather than relative (multiplicative) error?  
> **username_0**: @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.  

---

## 1 answers

### Answer by username_1 on 2024-05-13. Score: 2 | Accepted answer

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.

> **Comments:**
> **username_0**: 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).  

---

