It is shown that high order feedforward neural nets of constant depth with piecewise polynomial activation functions and arbitrary real weights can be simulated for boolean inputs and outputs by neural nets of a somewhat larger size and depth with heaviside gates and weights from {-1,0,1\}. This provides the first ... more >>>

We consider the threshold circuit complexity of computing the multiple product modulo m in threshold circuits. more >>>

Continuing the study of the relationship between $TC^0$, $AC^0$ and arithmetic circuits, started by Agrawal et al. (IEEE Conference on Computational Complexity'97), we answer a few questions left open in this paper. Our main result is that the classes Diff$AC^0$ and Gap$AC^0$ coincide, under poly-time, log-space, or log-time uniformity. From ... more >>>

Constant-depth arithmetic circuits have been defined and studied in [AAD97,ABL98]; these circuits yield the function classes #AC^0 and GapAC^0. These function classes in turn provide new characterizations of the computational power of threshold circuits, and provide a link between the circuit classes AC^0 (where many lower bounds are known) and ... more >>>

In this paper the computational power of a new type of gate is studied: winner-take-all gates. This work is motivated by the fact that the cost of implementing a winner-take-all gate in analog VLSI is about the same as that of implementing a threshold gate. We show that winner-take-all gates ... more >>>

The essential idea in the fast parallel computation of division and related problems is that of Chinese remainder representation (CRR) -- storing a number in the form of its residues modulo many small primes. Integer division provides one of the few natural examples of problems for which all currently-known constructions ... more >>>

Integer division has been known to lie in P-uniform TC^0 since the mid-1980's, and recently this was improved to DLOG-uniform TC^0. At the time that the results in this paper were proved and submitted for conference presentation, it was unknown whether division lay in DLOGTIME-uniform TC^0 (also known as FOM). ... more >>>

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

The sign-rank of a matrix A=[A_{ij}] with +/-1 entries is the least rank of a real matrix B=[B_{ij}] with A_{ij}B_{ij}>0 for all i,j. We obtain the first exponential lower bound on the sign-rank of a function in AC^0. Namely, let f(x,y)=\bigwedge_{i=1}^m\bigvee_{j=1}^{m^2} (x_{ij}\wedge y_{ij}). We show that the matrix [f(x,y)]_{x,y} has ... more >>>