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...

  • 1
    $\begingroup$ 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$. $\endgroup$ – Shaull Mar 20 '13 at 18:15
  • $\begingroup$ 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... $\endgroup$ – snikolenko Mar 20 '13 at 18:22
  • 1
    $\begingroup$ 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? $\endgroup$ – Shaull Mar 20 '13 at 18:28
  • 1
    $\begingroup$ 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$. $\endgroup$ – snikolenko Mar 20 '13 at 18:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.