A theorem on probabilistic constant depth Computations

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

A theorem on probabilistic constant depth Computations

Full text

Pdf (270 KB)

Source

Annual ACM Symposium on Theory of Computing archive
Proceedings of the sixteenth annual ACM symposium on Theory of computing table of contents

Pages: 471 - 474

Year of Publication: 1984

ISBN:0-89791-133-4

Authors

Miklos Ajtai
Michael Ben-Or

Sponsor

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 6, Downloads (12 Months): 40, Citation Count: 12

Additional Information:

references cited by index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/800057.808715 What is a DOI?

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	M. Ajtai, &Sgr;11-Formulae On Finite Structures, Annals of Pure and Applied Logic, 24 (1983) 1-48.
	2	C. G. Bennet and J. Gill, Relative to a Random Oracle A, PA @@@@ NPA @@@@ co-NPA with Probability 1, SIAM J. on Computing, 10 (1981) 96-113.
	3	A. K. Chandra, L. J. Stockmeyer, U. Viskin, A Complexity Theory for Unbounded Fanin Parallelism, Proc. 23rd FOCS, (1982) 1-13.
	4	L. Denenberg, Y. Gurevich and S. Shelah, Cardinalities Definable By Constant Depth Polynomial Size Circuits, TR-26-83, Harvard University, Oct. 1983.
	5	R. Fagin, M. M. Klawe, N. J. Pippenger and L. Stockmeyer, Bounded Depth, Polynomial Size Circuits for Symmetric Functions, IBM Research Report RJ 4040, Oct. 1983.
	6	M. Furst, J. B. Saxe and M. Sipser, Parity, Circuits, and the Polynomial Time Hierarchy, Proc. 22nd FOCS (1981) 260-270.
	7	Larry Stockmeyer, The complexity of approximate counting, Proceedings of the fifteenth annual ACM symposium on Theory of computing, p.118-126, December 1983 [doi>10.1145/800061.808740]

CITED BY 12

	Ravi B. Boppana, Threshold functions and bounded deptii monotone circuits, Proceedings of the sixteenth annual ACM symposium on Theory of computing, p.475-479, December 1984
	Philip D. MacKenzie , Quentin F. Stout, Ultra-fast expected time parallel algorithms, Proceedings of the second annual ACM-SIAM symposium on Discrete algorithms, p.414-423, January 28-30, 1991, San Francisco, California, United States
	Philip D. MacKenzie , Vijaya Ramachandran, Computational bounds for fundamental problems on general-purpose parallel models, Proceedings of the tenth annual ACM symposium on Parallel algorithms and architectures, p.152-163, June 28-July 02, 1998, Puerto Vallarta, Mexico
	Shiva Chaudhuri , Jaikumar Radhakrishnan, Deterministic restrictions in circuit complexity, Proceedings of the twenty-eighth annual ACM symposium on Theory of computing, p.30-36, May 22-24, 1996, Philadelphia, Pennsylvania, United States
	Amihood Amir , Richard Beigel , William Gasarch, Some connections between bounded query classes and non-uniform complexity, Information and Computation, v.186 n.1, p.104-139, 10 October 2003
	Philip D. MacKenzie, Load balancing requires &OHgr;(log*n) expected time, Proceedings of the third annual ACM-SIAM symposium on Discrete algorithms, p.94-99, September 1992, Orlando, Florida, United States
	David A. Mix Barrington , Neil Immerman , Clemens Lautemann , Nicole Schweikardt , Denis Thérien, First-order expressibility of languages with neutral letters or: the crane beach conjecture, Journal of Computer and System Sciences, v.70 n.2, p.101-127, March 2005
	Amit Sahai , Salil Vadhan, A complete problem for statistical zero knowledge, Journal of the ACM (JACM), v.50 n.2, p.196-249, March 2003
	Nicole Schweikardt, Arithmetic, first-order logic, and counting quantifiers, ACM Transactions on Computational Logic (TOCL), v.6 n.3, p.634-671, July 2005
	Shafi Goldwasser , Dan Gutfreund , Alexander Healy , Tali Kaufman , Guy N. Rothblum, Verifying and decoding in constant depth, Proceedings of the thirty-ninth annual ACM symposium on Theory of computing, June 11-13, 2007, San Diego, California, USA
	Arnaud Durand , Clemens Lautemann , Malika More, A simple proof of the polylog counting ability of first-order logic: guest column, ACM SIGACT News, v.38 n.4, December 2007
	Alexander D. Healy, Randomness-Efficient Sampling within NC1, Computational Complexity, v.17 n.1, p.3-37, April 2008