Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > KEYWORD > THRESHOLD GATES:
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