DIMACS Princeton Theory Seminar


Title:

Polynomial Vicinity Circuits and Nonlinear Lower Bounds

Speaker:

Kenneth W. Regan
State University of NY at Buffalo

Place:

Room 402, Computer Science Building
35 Olden Street
Princeton University.

Time:

12:10 PM (Lunch will be served at 11:45 AM)
Monday, March 17, 1997 **NOTE CHANGE OF DAY**

Contact:

rjl@cs.princeton.edu (Dick Lipton)

Abstract:

We study families of Boolean circuits with the property that the number of gates at distance $t$ fanning into or out of any given gate in a circuit is bounded above by a fixed polynomial in $t$. This polynomial, say $O(t^k)$, is independent of the input length $n$ or size of circuits $C_n$ in the family. We prove that such circuits require non-linear size $\Omega(n^{1+1/k}/\log n)$ to compute several basic functions, including sorting, finite-field arithmetic, and certain linear transformations. These results imply a ``size-vicinity tradeoff'' for circuits. Our proof develops a ``separator theorem'' in the style of Lipton and Tarjan [1979] for a new class of graphs, and our methods may have independent graph-theoretic interest.
Document last modified on March 12, 1997