Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with threshold circuit:
TR97-002 | 28th January 1997
Richard Beigel, Alexis Maciel

Upper and Lower Bounds for Some Depth-3 Circuit Classes

We investigate the complexity of depth-3 threshold circuits
with majority gates at the output, possibly negated AND
gates at level two, and MODm gates at level one. We show
that the fan-in of the AND gates can be reduced to O(log n)
in the case where ... more >>>

TR97-016 | 29th April 1997
Manindra Agrawal, Eric Allender, Samir Datta

On TC^0, AC^0, and Arithmetic Circuits

Continuing a line of investigation that has studied the
function classes #P, #SAC^1, #L, and #NC^1, we study the
class of functions #AC^0. One way to define #AC^0 is as the
class of functions computed by constant-depth polynomial-size
arithmetic circuits of unbounded fan-in addition ... more >>>

TR04-090 | 3rd November 2004
Kazuyuki Amano, Akira Maruoka

Better Simulation of Exponential Threshold Weights by Polynomial Weights

We give an explicit construction of depth two threshold circuit with polynomial weights and $\tilde{O}(n^5)$ gates that computes an arbitrary threshold function. We also give the construction of such circuits with $O(n^3/\log n)$ gates computing the COMPARISON and CARRY functions, and that with $O(n^4/\log n)$ gates computing the ADDITION function. ... more >>>

TR18-143 | 16th August 2018
Mark Bun, Justin Thaler

The Large-Error Approximate Degree of AC$^0$

We prove two new results about the inability of low-degree polynomials to uniformly approximate constant-depth circuits, even to slightly-better-than-trivial error. First, we prove a tight $\tilde{\Omega}(n^{1/2})$ lower bound on the threshold degree of the Surjectivity function on $n$ variables. This matches the best known threshold degree bound for any AC$^0$ ... more >>>

ISSN 1433-8092 | Imprint