An Approach to characterize the Regular Languages in TC0 with Linear Wires.
Christoph Behle, Andreas Krebs, Stephanie Reifferscheid · Electronic colloquium on computational complexity · 2009
We consider the regular languages recognized by weighted threshold circuits with a linear number of wires. We present a simple proof to show that parity cannot be computed by such circuits. Our proofs are based on an explicit construction to restrict the input of the circuit such that the value computed by the circuit are constant. The result is also a corollary of [IPS93] where a different proof method based on randomized restrictions is used.