Richard Beigel, Alexis Maciel

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

Kazuyuki Amano, Akira Maruoka

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

Natalia Dobrokhotova-Maikova, Alexander Kozachinskiy, Vladimir Podolskii

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