<p>A naive question perhaps: are there any results/references about $AC^0$ circuits with multiple outputs? Namely, I'm interested in the natural generalization of the Min-$AC^0_d$ problem (find a circuit of depth $d$ with minimal size that implements a given Boolean function). The generalization would be: find a circuit of depth $d$ with minimal size and $\log_2k$ outputs (or $k$ outputs if this encoding is more convenient -- $k$ is small anyway) that implements a given function $f:{\mathbb B}^n\to \{0,\ldots,k-1\}$.</p>

<p>I've tried googling but without effect (it's hard to google for $AC^0$ anyway). Any pointers would be much appreciated -- hardness results, inapproximability results, heuristics for solving the problem in practice...</p>

CC BY-SA 3.0
2013-03-20T18:15:57.137Z
Consider a mutiple-output circuit. Is there any reason not to add $\log k$ inputs that indicate which bit from the output you want? Then, you get a standard $AC^0$ circuit. I would think this translation enables translating most results to multiple-outputs, so the situation should not be different than $AC^0$.
Shaull
CC BY-SA 3.0
2013-03-20T18:22:39.153Z
Unfortunately there is (I'm interested in circuits with some additional structure that would be lost here). If you mean to say that this is the standard reduction and thus no work is done directly on circuits with multiple outputs, then thank you, this is probably the answer I'm looking for...
snikolenko
CC BY-SA 3.0
2013-03-20T18:28:30.707Z
I don't know if there is research on the topic, but I think this reduction may certainly reduce the interest in it.

But if you have additional structure, why not add specifics to the question?
Shaull
CC BY-SA 3.0
2013-03-20T18:55:25.723Z
Makes sense. :) I simply was quite sure that there's been no work on my specific problem, so I just asked if there are any general references.

I'm dealing with ordered $AC^0_3$ circuits, i.e. circuits satisfying the following property: there exists a linear ordering $\prec$ on level-1 $\lor$-gates such that if a level-2 $\land$-gate is connected to a level-1 $\lor$-gate $g$, it is also connected to all level-1 $\lor$-gates $g'$ with $g'\prec g$.
snikolenko
CC BY-SA 4.0
2022-04-20T16:39:37.403Z
@Shaull: Do you want to post a summary of your comments as an answer?
Joshua Grochow
CC BY-SA 4.0
2022-04-20T20:03:43.893Z
@JoshuaGrochow - it's not really my field, and I don't want to discourage potential answer. Anyhow, assuming my comments are correct, then this is not a research-level question, and should be migrated to cs.se.
Shaull
<cc.complexity-theory><circuit-complexity>
Multiple output $AC^0$ circuits?
snikolenko
# Multiple output $AC^0$ circuits?

(Asked by: username_0 on 2013-03-20)

A naive question perhaps: are there any results/references about $AC^0$ circuits with multiple outputs? Namely, I'm interested in the natural generalization of the Min-$AC^0\_d$ problem (find a circuit of depth $d$ with minimal size that implements a given Boolean function). The generalization would be: find a circuit of depth $d$ with minimal size and $\log\_2k$ outputs (or $k$ outputs if this encoding is more convenient -- $k$ is small anyway) that implements a given function $f:{\mathbb B}^n\to \{0,\ldots,k-1\}$.

I've tried googling but without effect (it's hard to google for $AC^0$ anyway). Any pointers would be much appreciated -- hardness results, inapproximability results, heuristics for solving the problem in practice...

**Tags:** cc.complexity-theory, circuit-complexity

> **Comments:**
> **username_1**: Consider a mutiple-output circuit. Is there any reason not to add $\log k$ inputs that indicate which bit from the output you want? Then, you get a standard $AC^0$ circuit. I would think this translation enables translating most results to multiple-outputs, so the situation should not be different than $AC^0$.  
> **username_0**: Unfortunately there is (I'm interested in circuits with some additional structure that would be lost here). If you mean to say that this is the standard reduction and thus no work is done directly on circuits with multiple outputs, then thank you, this is probably the answer I'm looking for...  
> **username_1**: I don't know if there is research on the topic, but I think this reduction may certainly reduce the interest in it.  But if you have additional structure, why not add specifics to the question?  
> **username_0**: Makes sense. :) I simply was quite sure that there's been no work on my specific problem, so I just asked if there are any general references.  I'm dealing with ordered $AC^0_3$ circuits, i.e. circuits satisfying the following property: there exists a linear ordering $\prec$ on level-1 $\lor$-gates such that if a level-2 $\land$-gate is connected to a level-1 $\lor$-gate $g$, it is also connected to all level-1 $\lor$-gates $g'$ with $g'\prec g$.  
> **username_2**: @username_1: Do you want to post a summary of your comments as an answer?  
> **username_1**: @JoshuaGrochow - it's not really my field, and I don't want to discourage potential answer. Anyhow, assuming my comments are correct, then this is not a research-level question, and should be migrated to cs.se.  

---

## 0 answers

