Shallow grates

AbstractThis note proves the existence of acyclic directed graphs of logarithmic depth, such that a superlinear number of input—output pairs remain connected after the removal of any sufficiently small linearly sized subset of the vertices. The technique can be used to prove the analogous, and asymptotically optimal, result for graphs of arbitrary depth, generalizing Schnitger's grate construction for graphs of large depth. Interest in this question relates to efforts to use graph theoretic methods to prove circuit complexity lower bounds for algebraic problems such as matrix multiplication. In particular, it establishes the optimality of Valiant's depth reduction technique as a method of reducing the number of connected input-output pairs. The proof uses Schnitger's grate construction, but also involves a lemma on expanding graphs which may be of independent interest