Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with linear wires:
TR09-085 | 14th September 2009
Christoph Behle, Andreas Krebs, Stephanie Reifferscheid

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

Revisions: 1

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 ... more >>>

ISSN 1433-8092 | Imprint