MONOTONE CIRCUITS FOR CONNECTIVITY HAVE DEPTH (LOG N)(2-O(1))

Authors
GOLDMANN M HASTAD J
Citation
M. Goldmann et J. Hastad, MONOTONE CIRCUITS FOR CONNECTIVITY HAVE DEPTH (LOG N)(2-O(1)), SIAM journal on computing, 27(5), 1998, pp. 1283-1294
Citations number
10
Categorie Soggetti
Computer Science Theory & Methods",Mathematics,"Computer Science Theory & Methods",Mathematics
Journal title
SIAM journal on computing → ACNP
ISSN journal
00975397
Volume
27
Issue
5
Year of publication
1998
Pages
1283 - 1294
Database
ISI
SICI code
0097-5397(1998)27:5<1283:MCFCHD>2.0.ZU;2-#
Abstract
We prove that a monotone circuit of size n(d) recognizing connectivity must have depth Omega((log n)(2)/log d). For formulas this implies de pth Omega((log n)(2)/log log n). For polynomial-size circuits the boun d becomes Omega((log n)(2)) which is optimal up to a constant.