ECCC-Report TR09-085https://eccc.weizmann.ac.il/report/2009/085Comments and Revisions published for TR09-085en-usMon, 28 Sep 2009 13:55:00 +0200
Revision 1
| An Approach to characterize the Regular Languages in TC0 with Linear Wires |
Christoph Behle,
Andreas Krebs,
Stephanie Reifferscheid
https://eccc.weizmann.ac.il/report/2009/085#revision1We 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.Mon, 28 Sep 2009 13:55:00 +0200https://eccc.weizmann.ac.il/report/2009/085#revision1
Paper TR09-085
| An Approach to characterize the Regular Languages in TC0 with Linear Wires |
Christoph Behle,
Andreas Krebs,
Stephanie Reifferscheid
https://eccc.weizmann.ac.il/report/2009/085We 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.Fri, 25 Sep 2009 17:51:17 +0300https://eccc.weizmann.ac.il/report/2009/085