Polynomial vicinity circuits and nonlinear lower bounds
Kenneth W. Regan · 2002
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 polynomial in t of some degree k. We prove that such circuits require size /spl Omega/(n/sup 1+1/k//log n) to compute several natural families of functions, including sorting, finite field arithmetic, and the "rigid linear transformations" of L. Valiant (1977). Our proof develops a "separator theorem" in the style of R. Lipton and R. Tarjan (1979) for a new class of graphs, and our methods may have independent graph-theoretic interest.