Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with threshold gates:
TR96-031 | 30th April 1996

Networks of Spiking Neurons: The Third Generation of Neural Network Models

The computational power of formal models for
networks of spiking neurons is compared with
that of other neural network models based on
McCulloch Pitts neurons (i.e. threshold gates)
respectively sigmoidal gates. In particular it
is shown that networks of spiking neurons are
... more >>>

TR98-070 | 7th December 1998
RĂ¼diger Reischuk

Can Large Fanin Circuits Perform Reliable Computations in the Presence of Noise?

For ordinary circuits with a fixed upper bound on the maximal fanin
of gates it has been shown that logarithmic redundancy is necessary and
sufficient to overcome random hardware faults.
Here, we consider the same question for unbounded fanin circuits that
in the noiseless case can compute ... more >>>

TR99-005 | 21st December 1998
Michael Schmitt

On the Sample Complexity for Nonoverlapping Neural Networks

A neural network is said to be nonoverlapping if there is at most one
edge outgoing from each node. We investigate the number of examples
that a learning algorithm needs when using nonoverlapping neural
networks as hypotheses. We derive bounds for this sample complexity
in terms of the Vapnik-Chervonenkis dimension. ... more >>>

TR15-123 | 31st July 2015
Xi Chen, Igor Carboni Oliveira, Rocco Servedio

Addition is exponentially harder than counting for shallow monotone circuits

Let $U_{k,N}$ denote the Boolean function which takes as input $k$ strings of $N$ bits each, representing $k$ numbers $a^{(1)},\dots,a^{(k)}$ in $\{0,1,\dots,2^{N}-1\}$, and outputs 1 if and only if $a^{(1)} + \cdots + a^{(k)} \geq 2^N.$ Let THR$_{t,n}$ denote a monotone unweighted threshold gate, i.e., the Boolean function which takes ... more >>>

TR20-017 | 18th February 2020
Alexander Kozachinskiy, Vladimir Podolskii

Multiparty Karchmer-Wigderson Games and Threshold Circuits

We suggest a generalization of Karchmer-Wigderson communication games to the multiparty setting. Our generalization turns out to be tightly connected to circuits consisting of threshold gates. This allows us to obtain new explicit constructions of such circuits for several functions. In particular, we provide an explicit (polynomial-time computable) log-depth monotone ... more >>>

ISSN 1433-8092 | Imprint