Why does the ouput of an NC0 circuit depend on only a constant number of input bits?

Question

I understand that NC0 circuits have a constant depth and bounded gate fan-in of two, but I'm struggling how to understand why the language is in NC0 iff there is a constant c such that for every n, there is a set c variables that determine it's membership.

Answer 1

An $\mathsf{NC}^0$ circuit with single output of depth $\ell$ has $O(2^\ell)$ nodes, and in particular can depend on at most $O(2^\ell)$ many input bits.

$\mathsf{NC}^0$ circuits become more interesting when we allow them to have many outputs. Amazingly, there are some things you can actually do with some circuits. Check out the classic paper Crypography in $\mathsf{NC}^0$ by Applebaum, Ishai, and Kushilevitz.