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

Vladimir Podolskii, Alexander A. Sherstov

A basic goal in complexity theory is to understand the communication complexity of number-on-the-forehead problems $f\colon(\{0,1\}^n)^{k}\to\{0,1\}$ with $k\gg\log n$ parties. We study the problems of inner product and set disjointness and determine their randomized communication complexity for every $k\geq\log n$, showing in both cases that $\Theta(1+\lceil\log n\rceil/\log\lceil1+k/\log n\rceil)$ bits are ... more >>>