# 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