A lower bound for the monotone depth of connectivity

Andrew Chi Chih Yao

doi:10.1109/SFCS.1994.365685

A lower bound for the monotone depth of connectivity

Andrew Chi Chih Yao

Faculty of Electronic and Information Engineering

Research output: Contribution to journal › Conference article › peer-review

10 Scopus citations

Abstract

We show that any monotone circuit for computing graph connectivity must have a depth greater than Ω((logn)³/²/loglogn). This proves that UCONN_n is not in monotone NC^l. The proof technique, which is an adaptation of Razborov's approximation method, is also used to derive lower bounds for a general class of graph problems.

Original language	English
Pages (from-to)	302-308
Number of pages	7
Journal	Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS
DOIs	https://doi.org/10.1109/SFCS.1994.365685
State	Published - 1994
Event	Proceedings of the 35th IEEE Annual Symposium on Foundations of Computer Science - Santa Fe, NM, USA Duration: 20 Nov 1994 → 22 Nov 1994

Access to Document

10.1109/SFCS.1994.365685

Cite this

@article{32aeedacb5324246863157bcac59d401,

title = "A lower bound for the monotone depth of connectivity",

abstract = "We show that any monotone circuit for computing graph connectivity must have a depth greater than Ω((logn)3/2/loglogn). This proves that UCONNn is not in monotone NCl. The proof technique, which is an adaptation of Razborov's approximation method, is also used to derive lower bounds for a general class of graph problems.",

author = "Yao, \{Andrew Chi Chih\}",

note = "Publisher Copyright: {\textcopyright} 1994 IEEE; Proceedings of the 35th IEEE Annual Symposium on Foundations of Computer Science ; Conference date: 20-11-1994 Through 22-11-1994",

year = "1994",

doi = "10.1109/SFCS.1994.365685",

language = "英语",

pages = "302--308",

journal = "Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS",

issn = "0272-5428",

publisher = "IEEE Computer Society",

}

TY - JOUR

T1 - A lower bound for the monotone depth of connectivity

AU - Yao, Andrew Chi Chih

PY - 1994

Y1 - 1994

N2 - We show that any monotone circuit for computing graph connectivity must have a depth greater than Ω((logn)3/2/loglogn). This proves that UCONNn is not in monotone NCl. The proof technique, which is an adaptation of Razborov's approximation method, is also used to derive lower bounds for a general class of graph problems.

AB - We show that any monotone circuit for computing graph connectivity must have a depth greater than Ω((logn)3/2/loglogn). This proves that UCONNn is not in monotone NCl. The proof technique, which is an adaptation of Razborov's approximation method, is also used to derive lower bounds for a general class of graph problems.

UR - https://www.scopus.com/pages/publications/0039933605

U2 - 10.1109/SFCS.1994.365685

DO - 10.1109/SFCS.1994.365685

M3 - 会议文章

AN - SCOPUS:0039933605

SN - 0272-5428

SP - 302

EP - 308

JO - Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS

JF - Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS

T2 - Proceedings of the 35th IEEE Annual Symposium on Foundations of Computer Science

Y2 - 20 November 1994 through 22 November 1994

ER -

A lower bound for the monotone depth of connectivity

Abstract

Access to Document

Other files and links

Fingerprint

Cite this