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