All reports by Author Benjamin Rossman:

__
TR15-065
| 18th April 2015
__

Benjamin Rossman, Rocco Servedio, Li-Yang Tan#### An average-case depth hierarchy theorem for Boolean circuits

__
TR14-145
| 4th November 2014
__

Yuan Li, Alexander Razborov, Benjamin Rossman#### On the $AC^0$ Complexity of Subgraph Isomorphism

Benjamin Rossman, Rocco Servedio, Li-Yang Tan

We prove an average-case depth hierarchy theorem for Boolean circuits over the standard basis of AND, OR, and NOT gates. Our hierarchy theorem says that for every $d \geq 2$, there is an explicit $n$-variable Boolean function $f$, computed by a linear-size depth-$d$ formula, which is such that any depth-$(d-1)$ ... more >>>

Yuan Li, Alexander Razborov, Benjamin Rossman

Let $P$ be a fixed graph (hereafter called a ``pattern''), and let

$Subgraph(P)$ denote the problem of deciding whether a given graph $G$

contains a subgraph isomorphic to $P$. We are interested in

$AC^0$-complexity of this problem, determined by the smallest possible exponent

$C(P)$ for which $Subgraph(P)$ possesses bounded-depth circuits ...
more >>>