# The ICICS/CS Reading Room

## UBC CS TR-92-03 Summary

- No on-line copy of this technical report is available.

- Shallow Grates, January 1992 Maria M. Klawe, 7 pages
This 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 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.

If you have any questions or comments regarding this page please send mail to
help@cs.ubc.ca.