In this work we investigate energy complexity, a Boolean function measure related to circuit complexity. Given a circuit ( C ) over the standard basis ( _2, _2, ), the energy complexity of ( C ), denoted by ( , EC , ( C ) ), is the maximum number of its activated inner gates over all inputs. The energy complexity of a Boolean function f, denoted by ( , EC , (f) ), is the minimum of ( , EC , ( C ) ) over all circuits ( C ) computing f.
Besides the standard basis of @math , there are other works considering about the energy complexity over bases of threshold gates @cite_14 @cite_6 @cite_5 and unate gates @cite_12 . In particular, since there exists similarity between human brain and energy complexity over threshold gate basis, a natural question readily comes up: can Boolean functions be computed with rather few activated gates over threshold gate basis? In order to answer this question, or more precisely, to give lower and upper bounds, plenty of studies were motivated @cite_2 @cite_8 @cite_3 @cite_7 @cite_14 . In addition, there are researches concerning the relationship between energy complexity and the largest fan-in gates @cite_1 . As for application, it is interesting to consider how to balance the error tolerance and the total energy of the circuit @cite_13 @cite_10 .
@cite_14 @cite_7 @cite_8 @cite_10 @cite_1 @cite_6 @cite_3 @cite_2 @cite_5 @cite_13 @cite_12
2117016759 2027328186 2080210666 2107998050 1495580177 1979569157
Circuits composed of threshold gates (McCulloch-Pitts neurons, or perceptrons) are simplified models of neural circuits with the advantage that they are theoretically more tractable than their biological counterparts. However, when such threshold circuits are designed to perform a specific computational task, they usually differ in one important respect from computations in the brain: they require very high activity. On average every second threshold gate fires (sets a 1 as output) during a computation. By contrast, the activity of neurons in the brain is much sparser, with only about 1 of neurons firing. This mismatch between threshold and neuronal circuits is due to the particular complexity measures (circuit size and circuit depth) that have been minimized in previous threshold circuit constructions. In this letter, we investigate a new complexity measure for threshold circuits, energy complexity, whose minimization yields computations with sparse activity. We prove that all computations by threshold circuits of polynomial size with entropy O(log n) can be restructured so that their energy complexity is reduced to a level near the entropy of circuit states. This entropy of circuit states is a novel circuit complexity measure, which is of interest not only in the context of threshold circuits but for circuit complexity in general. As an example of how this measure can be applied, we show that any polynomial size threshold circuit with entropy O(log n) can be simulated by a polynomial size threshold circuit of depth 3.Our results demonstrate that the structure of circuits that result from a minimization of their energy complexity is quite different from the structure that results from a minimization of previously considered complexity measures, and potentially closer to the structure of neural circuits in the nervous system. In particular, different pathways are activated in these circuits for different classes of inputs. This letter shows that such circuits with sparse activity have a surprisingly large computational power. Abstract We present a function in ACC 0 such that any depth-3 threshold circuit which computes this function and has AND gates at the bottom must have size n ω(log n ). Abstract We examine a powerful model of parallel computation: polynomial size threshold circuits of bounded depth (the gates compute threshold functions with polynomial weights). Lower bounds are given to separate polynomial size threshold circuits of depth 2 from polynomial size threshold circuits of depth 3 and from probabilistic polynomial size circuits of depth 2. With regard to the unreliability of bounded depth circuits, it is shown that the class of functions computed reliably with bounded depth circuits of unreliable ∨, ∧, ¬ gates is narrow. On the other hand, functions computable by bounded depth, polynomial-size threshold circuits can also be computed by such circuits of unreliable threshold gates. Furthermore we examine to what extent imprecise threshold gates (which behave unpredictably near the threshold value) can compute nontrivial functions in bounded depth and a bound is given for the permissible amount of imprecision. We also discuss threshold quantifiers and prove an undefinability result for graph connectivity. The paper investigates the complexity of depth-two circuits with threshold gates and consisting of two parts. First, we develop a method for deriving a lower bound on the size of depth two circuits with a threshold gate at the top and a certain type of gates at the bottom. We apply the method for circuits with symmetric gates at the bottom that compute the “inner product mod 2”, and obtain a lower bound of 1.3638n. Although our lower bound is slightly weaker than the best known lower bound of Ω(2n 2 n), which was recently proved by [5,6], our method has unique features: A lower bound is obtained by solving a certain linear program, and solving larger linear programs yield higher lower bounds. We also discuss the generalization of the proposed method. Second, we develop a simplified simulation of a depth-one threshold circuit with unbounded weights by a depth-two threshold circuit with small weights. Precisely, we give an explicit construction of depth-two circuits with small weights consist of On5 gates that compute an arbitrary threshold function. We also give the construction of such circuits with O(n3 log n) gates computing the COMPARISON and CARRY functions, and that with O(n4 log n) gates computing the ADDITION function. These improve the previously known constructions on its size and simplicity. A complexity measure for threshold circuits, called the energy complexity, has been proposed to measure an amount of energy consumed during computation in the brain. Biological neurons need more energy to transmit a ''spike'' than not to transmit one, and hence the energy complexity of a threshold circuit is defined as the number of gates in the circuit that output ''1'' during computation. Since the firing activity of neurons in the brain is quite sparse, the following question arises: what Boolean functions can or cannot be computed by threshold circuits with small energy complexity. In the paper, we partially answer the question, that is, we show that there exists a trade-off among three complexity measures of threshold circuits: the energy complexity, size, and depth. The trade-off implies an exponential lower bound on the size of constant-depth threshold circuits with small energy complexity for a large class of Boolean functions.