Monotone circuits for connectivity require super-logarithmic depth

ABSTRACT

We prove that every monotone circuit which tests st-connectivity of an undirected graph on n nodes has depth &OHgr;(log2n). This implies a superpolynomial (n&OHgr;(log n)) lower bound on the size of any monotone formula for st-connectivity. The proof draws intuition from a new characterization of circuit depth in terms of communication complexity. It uses counting arguments and Extremal Set Theory. Within the same framework, we also give a very simple and intuitive proof of a depth analogue of a theorem of Krapchenko concerning formula size lower bounds.

REFERENCES

• AB: N. Alon , R. B. Boppana, The monotone circuit complexity of Boolean functions, Combinatorica, v.7 n.1, p.1-22, Jan. 1987 [doi>10.1007/BF02579196]
• An: A.E. Andreev, "On a Method for Obtaining Lower Bounds for the Complexity of Individual Monotone Functions", Soy. Math. DokL 31, pp. 530-534 (1985),.
• Aj: M. Ajtai, "t~}-Formulae on Finite Structures'', Annals of Pure and Applied L09ic 24, pp. 1-48 (1983).
• AF: M. Ajtai, R. Fagin, Personal Communication.
• AKLLR: R. Aleliunas, R.M. Karp, R.J. Lipton, L. Lovasz, C. Rackoff, "'Random Walks, Universal Traversal Sequences, and the Complexity of Maze Problems", .Proceedings 0/20th FOC$, pp. 218-223 (1979).
• AKS: M. Ajtai , J. Komlós , E. Szemerédi, An 0(n log n) sorting network, Proceedings of the fifteenth annual ACM symposium on Theory of computing, p.1-9, December 1983 [doi>10.1145/800061.808726]
• BTh: B. Bollobás , A. Thomason, Threshold functions, Combinatorica, v.7 n.1, p.35-38, Jan. 1987 [doi>10.1007/BF02579198]
• FSS: M. Furst, J.B. Saxe, M. Sipser, "Parity Circuits and the Polynomial Time Hierarchy'', Proceedings of 22na FOES, pp. 260-270 (1981).
• H: J Hastad, Almost optimal lower bounds for small depth circuits, Proceedings of the eighteenth annual ACM symposium on Theory of computing, p.6-20, May 28-30, 1986, Berkeley, California, United States [doi>10.1145/12130.12132]
• KPPY: Maria Klawe , Wolfgang J. Paul , Nicholas Pippenger , Mihalis Yannakakis, On monotone formulae with restricted depth, Proceedings of the sixteenth annual ACM symposium on Theory of computing, p.480-487, December 1984 [doi>10.1145/800057.808717]
• K: V. Krapchenko, "A Method of Determining Lower Bounds for the Complexity of 11 Schemes", Math. Notes Acad. Sci. USSR, pp. 474-479 (1971).
• Ra: A.A. Razborov, "Lower Bounds for the Monotone Complexity of some Boolean Functions'', Soy. Math. Dokl. 31, pp. 354-357 (1985).
• Ru: W.L. Ruzzo, ""tee-Size Bounded Alternation", Journal of Computer and Syst. Sciences 21, pp. 218-235 (1980).
• ShS: E. Shamir, M. Snir, "On the Depth Complexity of Formulas", Math. Systems Theory 13, pp. 301-322 (1980).
• V: L.G. Valiant, "Short Monotone Formulae for the Majority Function", Journal of Algorithms 5, pp. 3611-3(10 (1984).
• Y1: Andrew Chi-Chih Yao, Some complexity questions related to distributive computing(Preliminary Report), Proceedings of the eleventh annual ACM symposium on Theory of computing, p.209-213, April 30-May 02, 1979, Atlanta, Georgia, United States [doi>10.1145/800135.804414]
• Y2: Andrew C-C. Yao, Separating the polynomial-time hierarchy by oracles, Proc. 26th annual symposium on Foundations of computer science, p.1-10, October 1985, Portland, Oregon, United States

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.1 Models of Computation
          Subjects: Unbounded-action devices (e.g., cellular automata, circuits, networks of machines)

Additional Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES

General Terms:
Algorithms, Theory