DIMACS Princeton Theory Seminar


Polynomial Vicinity Circuits and Nonlinear Lower Bounds


Kenneth W. Regan
State University of NY at Buffalo


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


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


rjl@cs.princeton.edu (Dick Lipton)


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