TY - GEN
T1 - Polynomial vicinity circuits and nonlinear lower bounds
AU - Regan, K. W.
N1 - Publisher Copyright:
© 1997 IEEE.
PY - 1997
Y1 - 1997
N2 - 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 ω(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.
AB - 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 ω(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.
UR - https://www.scopus.com/pages/publications/85058107557
U2 - 10.1109/CCC.1997.612301
DO - 10.1109/CCC.1997.612301
M3 - Conference contribution
AN - SCOPUS:85058107557
T3 - Proceedings of the Annual IEEE Conference on Computational Complexity
SP - 61
EP - 68
BT - Proceedings - 12th Annual IEEE Conference on Computational Complexity, CCC 1997 (Formerly: Structure in Complexity Theory Conference)
PB - IEEE Computer Society
T2 - 12th Annual IEEE Conference on Computational Complexity, CCC 1997
Y2 - 24 June 1997 through 27 June 1997
ER -