×

Energy-efficient threshold circuits for comparison functions. (English) Zbl 1258.68063

Summary: A threshold gate is a theoretical model of a neuron, and a threshold circuit is a theoretical model of a neural network. The energy \(e\) of a threshold circuit \(C\) is defined to be the maximum number of gates outputting ones, where the maximum is taken over all input assignments to \(C\). In this paper, we prove that the comparison function of \(2n\) variables is computable by a polynomial-weight threshold circuit \(C\) of energy \(e\), size \(s = O(n/\log n)\), depth \(d = O(n/(e \log n))\) for any \(e\), \(3\leq e\leq n/\log n/\lceil \log n\rceil\). Our result implies that one can construct an energy-efficient circuit computing the comparison function if it is allowable to use large depth.

MSC:

68Q05 Models of computation (Turing machines, etc.) (MSC2010)
94C10 Switching theory, application of Boolean algebra; Boolean functions (MSC2010)
92B20 Neural networks for/in biological studies, artificial life and related topics
PDFBibTeX XMLCite
Full Text: DOI