skip to main content
10.1145/73007.73025acmconferencesArticle/Chapter ViewAbstractPublication PagesstocConference Proceedingsconference-collections
Article
Free Access

Circuits and local computation

Authors Info & Claims
Published:01 February 1989Publication History

ABSTRACT

This paper contains two parts. In Part I, we show that polynomial-size monotone threshold circuits of depth k form a proper hierarchy in parameter k. This implies in particular that monotone TC0 is properly contained in NC1. In Part II, we introduce a new concept, called local function, which tries to characterize when a function can be efficiently computed using only localized processing elements. It serves as a unifying framework for viewing related and sometimes apparently unrelated results. In particular, it will be demonstrated that the recent results on lower bounds for monotone circuits by Razborov [Ra1] and Karchmer and Wigderson [KW], as well as a main theorem in Part I of this paper, can be regarded as proving certain functions to be nonlocal. We will also suggest an approach based on locality for attacking the conjecture that (nonmonotone) TC0 is properly contained in NC1.

References

  1. Ab.H. Abelson, "Towards a theory of local and global in computation," Theoretical Computer Science 6 (1978), 41-67.Google ScholarGoogle ScholarCross RefCross Ref
  2. Aj.M. Ajtai, "E} formulae on finite structures," Annals of Pure and Applied Logic 24 (1983), 1-48.Google ScholarGoogle ScholarCross RefCross Ref
  3. AG.M. Ajtai and Y. Gurevich, "Monotone versus positive," Journal of A C'M 34 (1987), 1004- 1015. Google ScholarGoogle ScholarDigital LibraryDigital Library
  4. An.A.E. Andreev, "On one method of obtaining lower bounds of individual monotone functions,'' Dokl. Ak. Nauk. 282 (1985), 1033- 1037. (Sov. Math. Dokl. 31 (1985), 530-534.)Google ScholarGoogle Scholar
  5. Ba.D.A. Barrington,"Bounded-width polynomial size branching programs recogni, ze exactly those languages in NC1,'' Proceedings of 18ih ACM Symposium on Theory of Computing (1986), 1-5. Google ScholarGoogle ScholarDigital LibraryDigital Library
  6. Bo.R. Boppana, "Threshold functions and bounded depth monotone circuits," Proceedings of 16th A CM Symposium on Theory of Computing (1984), 475-479. Google ScholarGoogle ScholarDigital LibraryDigital Library
  7. Br.J. Bruck, "Harmonic analysis of polynomial threshold functions", preprint, IBM Almaden Research Center, July 1988.Google ScholarGoogle Scholar
  8. CSV.A. K. Chandra, L. J. Stockmeyer, and U. Vishkin, "Constant depth reducibility," E{AM J. on Computing 13 (1984), 423-439.Google ScholarGoogle Scholar
  9. FSS.M. Furst, J. Saxe, and M. Sipser, "Parity, circuits, and the polynomial-time hierarchy," Proceedings 22th Annual IEEE Symposium on Foundations of Computer Science, 1981, 260-270.Google ScholarGoogle Scholar
  10. HMPST.A. Hajnal, W. Maass, P. Pudl~k, M Szegedy, and G. TurSn, "Threshold circuits of bounded depth," Proceedings 28th Annual IEEE Symposium on Foundations of Computer Science, 1987, 99-110.Google ScholarGoogle Scholar
  11. H.J. Hastad, "Almost optimal lower bounds for small depth circuits," Proceedings of 18th ACM Symposium on Theory of Computing (1986), 6-20. Google ScholarGoogle ScholarDigital LibraryDigital Library
  12. HK.J.-W. Hong and H. T. Kung, "I/O complexity: The red-blue pebble game," Proceedings of 13ih A CM Symposium on Theory of Computing (1981), 326-333. Google ScholarGoogle ScholarDigital LibraryDigital Library
  13. KW.M. Karchmer and A. Wigderson, "Monotone circuits for connectivity require superlogarithmic depth," Proceedings of 20th A CM Symposium on Theory of Computing (1988), 539-550. Google ScholarGoogle ScholarDigital LibraryDigital Library
  14. KPPY.M. Klawe, W. Paul, N. Pippenger, and M. Yannakakis, "On monotone formulae with restricted depth," Proceedings of 16ih A CM Symposium on Theory ojf Computing (1984), 480-487. Google ScholarGoogle ScholarDigital LibraryDigital Library
  15. MP.M. Minsky and $. A. Papert, Perceptrons, MiT Press, Cambridge, Massachusetts, 1969. Google ScholarGoogle ScholarDigital LibraryDigital Library
  16. PS.I. Parberry and G. Schnitger, "Parallel computation with threshold functions," Journal of Computer and System Science 36 (1988), 278-302. Google ScholarGoogle ScholarDigital LibraryDigital Library
  17. Ra1.A.A. Razborov, "Lower bounds for the monotone complexity of some Boolean funtions," Dokl. Akad. Nauk. 281 (1985), 798- 801. (Soy. Math. Dokl. 31 (1985), 354-357.)Google ScholarGoogle Scholar
  18. Ra2.A.A. Razborov, "Lower bounds for the size of circuits of bounded depth with basis {A, ~)}," to appear in Mat. Zametki. (Mathematical Notes of the Soviet Academy of $ci- ~nC~).Google ScholarGoogle Scholar
  19. Re.J. Reif, "On threshold circuits and polynomial computations," Proceedings of ~nd Structure in Compleziiy Theory Conference, 1987, 118-125.Google ScholarGoogle Scholar
  20. Si.M. Sipser, "Borel sets and circuit complexity,'' Proceedings of 15ih A CM Symposium on Theory of Computing (1983), 330-335. Google ScholarGoogle ScholarDigital LibraryDigital Library
  21. Sm.R. Smolensky, "Algorithmic methods in the theory of lower bounds for Boolean circuit complexity," Proceedings of l gih A CM Symposium on Theory of Computing (1987), 77- 82. Google ScholarGoogle ScholarDigital LibraryDigital Library
  22. T.I~. Tardos, "The gap between monotone and non-monotone circuit complexity is exponential,'' Combinatorica 8 (1988), 141-142.Google ScholarGoogle ScholarCross RefCross Ref
  23. U.Y. Uesaka, "Analog perceptron: its decomposition and order," Information and Control 27 (1975), 199-217.Google ScholarGoogle ScholarCross RefCross Ref
  24. Y.A.C. Yao, "Separating the polynomiM-time hierarchy by oracles," Proceedings 261h Annual IEEE Symposium on Foundations of Computer Science, 1985, 1-10. Google ScholarGoogle ScholarDigital LibraryDigital Library

Index Terms

  1. Circuits and local computation

            Recommendations

            Comments

            Login options

            Check if you have access through your login credentials or your institution to get full access on this article.

            Sign in
            • Published in

              cover image ACM Conferences
              STOC '89: Proceedings of the twenty-first annual ACM symposium on Theory of computing
              February 1989
              600 pages
              ISBN:0897913078
              DOI:10.1145/73007

              Copyright © 1989 ACM

              Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

              Publisher

              Association for Computing Machinery

              New York, NY, United States

              Publication History

              • Published: 1 February 1989

              Permissions

              Request permissions about this article.

              Request Permissions

              Check for updates

              Qualifiers

              • Article

              Acceptance Rates

              STOC '89 Paper Acceptance Rate56of196submissions,29%Overall Acceptance Rate1,469of4,586submissions,32%

              Upcoming Conference

              STOC '24
              56th Annual ACM Symposium on Theory of Computing (STOC 2024)
              June 24 - 28, 2024
              Vancouver , BC , Canada

            PDF Format

            View or Download as a PDF file.

            PDF

            eReader

            View online with eReader.

            eReader