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.
- Ab.H. Abelson, "Towards a theory of local and global in computation," Theoretical Computer Science 6 (1978), 41-67.Google ScholarCross Ref
- Aj.M. Ajtai, "E} formulae on finite structures," Annals of Pure and Applied Logic 24 (1983), 1-48.Google ScholarCross Ref
- AG.M. Ajtai and Y. Gurevich, "Monotone versus positive," Journal of A C'M 34 (1987), 1004- 1015. Google ScholarDigital Library
- 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 Scholar
- 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 ScholarDigital Library
- Bo.R. Boppana, "Threshold functions and bounded depth monotone circuits," Proceedings of 16th A CM Symposium on Theory of Computing (1984), 475-479. Google ScholarDigital Library
- Br.J. Bruck, "Harmonic analysis of polynomial threshold functions", preprint, IBM Almaden Research Center, July 1988.Google Scholar
- CSV.A. K. Chandra, L. J. Stockmeyer, and U. Vishkin, "Constant depth reducibility," E{AM J. on Computing 13 (1984), 423-439.Google Scholar
- 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 Scholar
- 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 Scholar
- H.J. Hastad, "Almost optimal lower bounds for small depth circuits," Proceedings of 18th ACM Symposium on Theory of Computing (1986), 6-20. Google ScholarDigital Library
- 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 ScholarDigital Library
- 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 ScholarDigital Library
- 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 ScholarDigital Library
- MP.M. Minsky and $. A. Papert, Perceptrons, MiT Press, Cambridge, Massachusetts, 1969. Google ScholarDigital Library
- PS.I. Parberry and G. Schnitger, "Parallel computation with threshold functions," Journal of Computer and System Science 36 (1988), 278-302. Google ScholarDigital Library
- 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 Scholar
- 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 Scholar
- Re.J. Reif, "On threshold circuits and polynomial computations," Proceedings of ~nd Structure in Compleziiy Theory Conference, 1987, 118-125.Google Scholar
- Si.M. Sipser, "Borel sets and circuit complexity,'' Proceedings of 15ih A CM Symposium on Theory of Computing (1983), 330-335. Google ScholarDigital Library
- 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 ScholarDigital Library
- T.I~. Tardos, "The gap between monotone and non-monotone circuit complexity is exponential,'' Combinatorica 8 (1988), 141-142.Google ScholarCross Ref
- U.Y. Uesaka, "Analog perceptron: its decomposition and order," Information and Control 27 (1975), 199-217.Google ScholarCross Ref
- 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 ScholarDigital Library
Index Terms
Circuits and local computation
Recommendations
Constant-Depth Circuits vs. Monotone Circuits
CCC '23: Proceedings of the conference on Proceedings of the 38th Computational Complexity ConferenceWe establish new separations between the power of monotone and general (non-monotone) Boolean circuits:
• For every k ≥ 1, there is a monotone function in AC0 (constant-depth poly-size circuits) that requires monotone circuits of depth Ω(logk n). ...
Delegating computation: interactive proofs for muggles
STOC '08: Proceedings of the fortieth annual ACM symposium on Theory of computingIn this work we study interactive proofs for tractable languages. The (honest) prover should be efficient and run in polynomial time, or in other words a "muggle". The verifier should be super-efficient and run in nearly-linear time. These proof systems ...
Collapse of the Hierarchy of Constant-Depth Exact Quantum Circuits
We study the quantum complexity class $${\mathsf{QNC}^\mathsf{0}_\mathsf{f}}$$QNCf0 of quantum operations implementable exactly by constant-depth polynomial-size quantum circuits with unbounded fan-out gates. Our main result is that the quantum OR ...
Comments