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

Manindra Agrawal, Eric Allender, Samir Datta

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

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

Mark Bun, Justin Thaler

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

Pooya Hatami, William Hoza, Avishay Tal, Roei Tell

We present new constructions of pseudorandom generators (PRGs) for two of the most widely-studied non-uniform circuit classes in complexity theory. Our main result is a construction of the first non-trivial PRG for linear threshold (LTF) circuits of arbitrary constant depth and super-linear size. This PRG fools circuits with depth $d\in\mathbb{N}$ ... more >>>

Zhiyuan Fan, Jiatu Li, Tianqi Yang

How much computational resource do we need for cryptography? This is an important question of both theoretical and practical interests. In this paper, we study the problem on pseudorandom functions (PRFs) in the context of circuit complexity. Perhaps surprisingly, we prove extremely tight upper and lower bounds in various circuit ... more >>>

Pooya Hatami, William Hoza, Avishay Tal, Roei Tell

For $n \in \mathbb{N}$ and $d = o(\log \log n)$, we prove that there is a Boolean function $F$ on $n$ bits and a value $\gamma = 2^{-\Theta(d)}$ such that $F$ can be computed by a uniform depth-$(d + 1)$ $\text{AC}^0$ circuit with $O(n)$ wires, but $F$ cannot be computed ... more >>>