I was curious if something like that is known or was studied.

Let's call a function simple if it is computable by $AC_0$ circuit of depth $\leq d$ and size $\leq n^k$ for fixed $k,d$.

Now let's consider general circuits: gates are $\{\vee,\wedge,\neg\}$ of fun-in at most $2$, no depth restrictions.

Let's call a circuit nice if in all gates it computes only simple functions. That immediately implies that if a function is not simple it can not be computed by a nice circuit.

My question is: do we know some simple function that is not computable by linear-size nice circuit? How about other definitions of simple or different models, like arithmetic circuits?

  • 3
    $\begingroup$ What does "in all gates it computes only simple functions" mean? If "the functions computed at all gates are simple", then nice circuits = $AC^0$ circuits. If this means "each gate must be simple", then nice circucits include general $\{\lor,\land,\neg\}$ circuits. $\endgroup$
    – Stasys
    Sep 1 '17 at 12:12
  • 3
    $\begingroup$ The output gate is also a gate. $\endgroup$
    – Stasys
    Sep 1 '17 at 13:00
  • 3
    $\begingroup$ "Yes, I've meant that functions at all gates are simple". So, if $f$ is a simple function, why it cannot be computed by a nice circuit with just 1 gate $f$? If only gates (not the functions computed at these gates, as you require) must be simple, then you are actually asking much more than for a nonlinear lower bound on the size of $\{\lor,\land,\neg\}$ circuits for an $AC^0$ function. But we do not know such a bound even for functions in NP. $\endgroup$
    – Stasys
    Sep 1 '17 at 15:40
  • 4
    $\begingroup$ It seems that the op is asking whether there is a function in AC_0 that is know not to be computable by a fan-in 2 circuit of linear size with the restriction that each gate computes an AC_0 function. Without this restriction the answer seems to be unknown even for functions in NP. $\endgroup$ Sep 1 '17 at 22:50
  • 2
    $\begingroup$ @Mateus: so, we have standard fanin-in 2 circuits with a semantic restriction that at no gate a function outside $AC^0$ (like parity) can be computed. This already makes sense. To understand the model, one needs to understand "fanin vs. depth" tradeoff: examples of $AC^0$ functions $f$ requiring many gates in $AC^0$ (constant depth) circuits but having small nice circuits of quickly growing depth. Without the restriction "nice", already parity function shows the gap. $\endgroup$
    – Stasys
    Sep 2 '17 at 9:08

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.