Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #1 to TR09-085 | 28th September 2009 13:54

An Approach to characterize the Regular Languages in TC0 with Linear Wires

RSS-Feed




Revision #1
Authors: Christoph Behle, Andreas Krebs, Stephanie Reifferscheid
Accepted on: 28th September 2009 13:55
Downloads: 1684
Keywords: 


Abstract:

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.



Changes to previous version:

Remove misleading "symmetric Boolean functions". Spezified that the depth remains unchanged in lemma 1.


Paper:

TR09-085 | 14th September 2009 15:57

An Approach to characterize the Regular Languages in TC0 with Linear Wires





TR09-085
Authors: Christoph Behle, Andreas Krebs, Stephanie Reifferscheid
Publication: 25th September 2009 17:51
Downloads: 1484
Keywords: 


Abstract:

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.



ISSN 1433-8092 | Imprint