Title :
A lower bound for the monotone depth of connectivity
Author :
Yao, Andrew Chi-Chih
Author_Institution :
Dept. of Comput. Sci., Princeton Univ., NJ, USA
Abstract :
We show that any monotone circuit for computing graph connectivity must have a depth greater than Ω((log n)3/2/ log log n). This proves that UCONNn is not in monotone NC1. 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
Keywords :
computational complexity; computational geometry; graph theory; Razborov´s approximation method; computational complexity; computational geometry; graph connectivity; graph problems; lower bound; lower bounds; monotone circuit; monotone depth of connectivity; proof technique; Approximation methods; Boolean functions; Circuit analysis computing; Computer science; Error analysis; Game theory; Polynomials;
Conference_Titel :
Foundations of Computer Science, 1994 Proceedings., 35th Annual Symposium on
Conference_Location :
Santa Fe, NM
Print_ISBN :
0-8186-6580-7
DOI :
10.1109/SFCS.1994.365685
