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

Claudia Bertram, Thomas Hofmeister

We consider the threshold circuit complexity of computing

the multiple product modulo m in threshold circuits.

Andris Ambainis, David Mix Barrington, Huong LeThanh

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

Eric Allender, Andris Ambainis, David Mix Barrington, Samir Datta, Huong LeThanh

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

Eric Allender, David Mix Barrington

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

Eric Allender, David Mix Barrington, William Hesse

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

Kei Uchizawa, Rodney Douglas

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

Alexander Razborov, Alexander A. Sherstov

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

Ruiwen Chen, Valentine Kabanets

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

Kristoffer Arnsfelt Hansen, Vladimir Podolskii

We study the complexity of computing Boolean functions on general

Boolean domains by polynomial threshold functions (PTFs). A typical

example of a general Boolean domain is $\{1,2\}^n$. We are mainly

interested in the length (the number of monomials) of PTFs, with

their degree and weight being of secondary interest. We ...
more >>>

Eric Allender, Nikhil Balaji, Samir Datta

We present improved uniform TC$^0$ circuits for division, matrix powering, and related problems, where the improvement is in terms of ``majority depth'' (initially studied by Maciel and Therien). As a corollary, we obtain improved bounds on the complexity of certain problems involving arithmetic circuits, which are known to lie in ... more >>>

Eric Allender, Anna Gal, Ian Mertz

We consider arithmetic complexity classes that are in some sense dual to the classes VP(Fp) that were introduced by Valiant. This provides new characterizations of the complexity classes ACC^1 and TC^1, and also provides a compelling example of

a class of high-degree polynomials that can be simulated via arithmetic circuits ...
more >>>

Daniel Kane, Ryan Williams

In order to formally understand the power of neural computing, we first need to crack the frontier of threshold circuits with two and three layers, a regime that has been surprisingly intractable to analyze. We prove the first super-linear gate lower bounds and the first super-quadratic wire lower bounds for ... more >>>

Ruiwen Chen, Rahul Santhanam, Srikanth Srinivasan

We show average-case lower bounds for explicit Boolean functions against bounded-depth threshold circuits with a superlinear number of wires. We show that for each integer d > 1, there is \epsilon_d > 0 such that Parity has correlation at most 1/n^{\Omega(1)} with depth-d threshold circuits which have at most

n^{1+\epsilon_d} ...
more >>>

Mark Bun, Justin Thaler

The sign-rank of a matrix $A$ with entries in $\{-1, +1\}$ is the least rank of a real matrix $B$ with $A_{ij} \cdot B_{ij} > 0$ for all $i, j$. Razborov and Sherstov (2008) gave the first exponential lower bounds on the sign-rank of a function in AC$^0$, answering an ... more >>>

Mark Bun, Justin Thaler

Threshold weight, margin complexity, and Majority-of-Threshold circuit size are basic complexity measures of Boolean functions that arise in learning theory, communication complexity, and circuit complexity. Each of these measures might exhibit a chasm at depth three: namely, all polynomial size Boolean circuits of depth two have polynomial complexity under the ... more >>>

Arkadev Chattopadhyay, Nikhil Mande

Proving super-polynomial lower bounds against depth-2 threshold circuits of the form THR of THR is a well-known open problem that represents a frontier of our understanding in boolean circuit complexity. By contrast, exponential lower bounds on the size of THR of MAJ circuits were shown by Razborov and Sherstov (SIAM ... more >>>

Arkadev Chattopadhyay, Meena Mahajan, Nikhil Mande, Nitin Saurabh

We demonstrate a lower bound technique for linear decision lists, which are decision lists where the queries are arbitrary linear threshold functions.

We use this technique to prove an explicit lower bound by showing that any linear decision list computing the function $MAJ \circ XOR$ requires size $2^{0.18 n}$. This ...
more >>>

Alexander Kozachinskiy, Vladimir Podolskii

We suggest a generalization of Karchmer-Wigderson communication games to the multiparty setting. Our generalization turns out to be tightly connected to circuits consisting of threshold gates. This allows us to obtain new explicit constructions of such circuits for several functions. In particular, we provide an explicit (polynomial-time computable) log-depth monotone ... more >>>

Gal Vardi, Ohad Shamir

In studying the expressiveness of neural networks, an important question is whether there are functions which can only be approximated by sufficiently deep networks, assuming their size is bounded. However, for constant depths, existing results are limited to depths $2$ and $3$, and achieving results for higher depths has been ... more >>>

tatsuie tsukiji

This paper aims to derandomize the following problems in the smoothed analysis of Spielman and Teng. Learn Disjunctive Normal Form (DNF), invert Fourier Transforms (FT), and verify small circuits' unsatisfiability. Learning algorithms must predict a future observation from the only $m$ i.i.d. samples of a fixed but unknown joint-distribution $P(G(x),y)$ ... more >>>

Daniel Avraham , Amir Yehudayoff

A matrix is blocky if it is a blowup of a permutation matrix. The blocky rank of a matrix M is the minimum number of blocky matrices that linearly span M. Hambardzumyan, Hatami and Hatami defined blocky rank and showed that it is connected to communication complexity and operator theory. ... more >>>