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

电子与信息学部

科研成果: 期刊稿件 › 会议文章 › 同行评审

10 引用（Scopus）

摘要

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.

源语言	英语
页（从-至）	302-308
页数	7
期刊	Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS
DOI	https://doi.org/10.1109/SFCS.1994.365685
出版状态	已出版 - 1994
活动	Proceedings of the 35th IEEE Annual Symposium on Foundations of Computer Science - Santa Fe, NM, USA 期限: 20 11月 1994 → 22 11月 1994

访问文件

10.1109/SFCS.1994.365685

其它文件与链接

链接到 Scopus 的出版物

引用此

@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

摘要

访问文件

其它文件与链接

学术指纹

引用此