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

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

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

A family of Boolean circuits $\{C_n\}_{n\geq 0}$ is called \emph{$\gamma(n)$-weakly uniform} if
there is a polynomial-time algorithm for deciding the direct-connection language of every $C_n$,
given \emph{advice} of size $\gamma(n)$. This is a relaxation of the usual notion of uniformity, which allows one
to interpolate between complete uniformity (when $\gamma(n)=0$) ... more >>>