Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > KEYWORD > CONSTANT DEPTH:
Reports tagged with constant depth:
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 >>>

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

TR22-116 | 17th August 2022
Natalia Dobrokhotova-Maikova, Alexander Kozachinskiy, Vladimir Podolskii

#### Constant-Depth Sorting Networks

In this paper, we address sorting networks that are constructed from comparators of arity $k > 2$. That is, in our setting the arity of the comparators -- or, in other words, the number of inputs that can be sorted at the unit cost -- is a parameter. We study ... more >>>

ISSN 1433-8092 | Imprint