Almost optimal lower bounds for small depth circuits

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Almost optimal lower bounds for small depth circuits

Full text

Pdf (1.03 MB)

Source

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

Berkeley, California, United States

Pages: 6 - 20

Year of Publication: 1986

ISBN:0-89791-193-8

Author

J Hastad

Applied Mathematics department and Laboratory of Computer Science, MIT

Sponsor

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 7, Downloads (12 Months): 55, Citation Count: 39

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/12130.12132 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.

	Aj	Ajtai M. "Z~-Formulae on Finite Structures", Annals of Pure and Applied Logic 24(1983) 1-48
	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	Andreev A.E. "On one method of obtaining lower bounds of individual monotone function complexity" Dokl. Ak. Nauk. 282 (1085)) pp 1033-1037.
	B	Ravi B Boppana, Threshold functions and bounded depth monotone circuits, Journal of Computer and System Sciences, v.32 n.2, p.222-229, April 1986 [doi>10.1016/0022-0000(86)90027-9]
	C	J Y Cai, With probability one, a random oracle separates PSPACE from the polynomial-time hierarchy, Proceedings of the eighteenth annual ACM symposium on Theory of computing, p.21-29, May 28-30, 1986, Berkeley, California, United States [doi>10.1145/12130.12133]
	FSS	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]
	R	Michael Sipser, Borel sets and circuit complexity, Proceedings of the fifteenth annual ACM symposium on Theory of computing, p.61-69, December 1983 [doi>10.1145/800061.808733]
	V	L. G. Valiant, Exponential lower bounds for restricted monotone circuits, Proceedings of the fifteenth annual ACM symposium on Theory of computing, p.110-117, December 1983 [doi>10.1145/800061.808739]
	Y	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

CITED BY 39

	Ran Raz , Amir Shpilka, Lower bounds for matrix product, in bounded depth circuits with arbitrary gates, Proceedings of the thirty-third annual ACM symposium on Theory of computing, p.409-418, July 2001, Hersonissos, Greece
	D. Barrington , D. Therien, Finite monoids and the fine structure of NC¹, Proceedings of the nineteenth annual ACM conference on Theory of computing, p.101-109, January 1987, New York, New York, United States
	S. R. Buss, The Boolean formula value problem is in ALOGTIME, Proceedings of the nineteenth annual ACM conference on Theory of computing, p.123-131, January 1987, New York, New York, United States
	David R. Karger, Global min-cuts in RNC, and other ramifications of a simple min-out algorithm, Proceedings of the fourth annual ACM-SIAM Symposium on Discrete algorithms, p.21-30, January 25-27, 1993, Austin, Texas, United States
	Ker-I Ko, Relativized polynomial time hierarchies having exactly K levels, Proceedings of the twentieth annual ACM symposium on Theory of computing, p.245-253, May 02-04, 1988, Chicago, Illinois, United States
	Paul Beame , Johan Hastad, Optimal bounds for decision problems on the CRCW PRAM, Journal of the ACM (JACM), v.36 n.3, p.643-670, July 1989
	David A. Mix Barrington , Denis Thérien, Finite monoids and the fine structure of NC1, Journal of the ACM (JACM), v.35 n.4, p.941-952, Oct. 1988
	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
	P Beame, Limits on the power of concurrent-write parallel machines, Proceedings of the eighteenth annual ACM symposium on Theory of computing, p.169-176, May 28-30, 1986, Berkeley, California, United States
	Rüdiger Reischuk, Simultaneous WRITES of parallel random access machines do not help to compute simple arithmetic functions, Journal of the ACM (JACM), v.34 n.1, p.163-178, Jan. 1987
	Danny Harnik , Ran Raz, Higher lower bounds on monotone size, Proceedings of the thirty-second annual ACM symposium on Theory of computing, p.378-387, May 21-23, 2000, Portland, Oregon, United States
	R. Smolensky, Algebraic methods in the theory of lower bounds for Boolean circuit complexity, Proceedings of the nineteenth annual ACM conference on Theory of computing, p.77-82, January 1987, New York, New York, United States
	M. Karchmer , A. Wigderson, Characterizing non-deterministic circuit size, Proceedings of the twenty-fifth annual ACM symposium on Theory of computing, p.532-540, May 16-18, 1993, San Diego, California, United States
	Richard Beigel, When do extra majority gates help?, Proceedings of the twenty-fourth annual ACM symposium on Theory of computing, p.450-454, May 04-06, 1992, Victoria, British Columbia, Canada
	Russell Impagliazzo , Ramamohan Paturi , Michael E. Saks, Size-depth trade-offs for threshold circuits, Proceedings of the twenty-fifth annual ACM symposium on Theory of computing, p.541-550, May 16-18, 1993, San Diego, California, United States
	Ramamohan Paturi , Michael E. Saks , Francis Zane, Exponential lower bounds for depth 3 Boolean circuits, Proceedings of the twenty-ninth annual ACM symposium on Theory of computing, p.86-91, May 04-06, 1997, El Paso, Texas, United States
	Ingo Wegener, On the complexity of branching programs and decision trees for clique functions, Journal of the ACM (JACM), v.35 n.2, p.461-471, April 1988
	M Ajtai , L Babai , P Hajnal , J Komlos , P Pudlak, Two lower bounds for branching programs, Proceedings of the eighteenth annual ACM symposium on Theory of computing, p.30-38, May 28-30, 1986, Berkeley, California, United States
	Ming Li , Yaacov Yesha, New lower bounds for parallel computation, Journal of the ACM (JACM), v.36 n.3, p.671-680, July 1989
	Mauricio Karchmer , Avi Wigderson, Monotone circuits for connectivity require super-logarithmic depth, Proceedings of the twentieth annual ACM symposium on Theory of computing, p.539-550, May 02-04, 1988, Chicago, Illinois, United States
	A. C. Yao, Circuits and local computation, Proceedings of the twenty-first annual ACM symposium on Theory of computing, p.186-196, May 14-17, 1989, Seattle, Washington, United States
	Amir Shpilka, Affine projections of symmetric polynomials, Journal of Computer and System Sciences, v.65 n.4, p.639-659, December 2002
	Eli Ben-Sasson, Hard examples for the bounded depth Frege proof system, Computational Complexity, v.11 n.3/4, p.109-136, March 2003
	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
	M. Szegedy, Functions with bounded symmetric communication complexity and circuits with mod m gates, Proceedings of the twenty-second annual ACM symposium on Theory of computing, p.278-286, May 13-17, 1990, Baltimore, Maryland, United States
	Vince Grolmusz, A weight-size trade-off for circuits with MOD m gates, Proceedings of the twenty-sixth annual ACM symposium on Theory of computing, p.68-74, May 23-25, 1994, Montreal, Quebec, Canada
	Nicholas Pippenger, The complexity of computations by networks, IBM Journal of Research and Development, v.31 n.2, p.235-243, March 1987
	Jin-Yi Cai , Osamu Watanabe, Relativized collapsing between BPP and PH under stringent oracle access, Information Processing Letters, v.90 n.3, p.147-154, 16 May 2004
	Ramamohan Paturi , Pavel Pudlák , Michael E. Saks , Francis Zane, An improved exponential-time algorithm for k-SAT, Journal of the ACM (JACM), v.52 n.3, p.337-364, May 2005
	Sorin Draghici, On the capabilities of neural networks using limited precision weights, Neural Networks, v.15 n.3, p.395-414, April 2002
	Matthias Krause, On the computational power of Boolean decision lists, Computational Complexity, v.14 n.4, p.362-375, March 2006
	P. Beame , J. Hastad, Optimal bounds for decision problems on the CRCW PRAM, Proceedings of the nineteenth annual ACM conference on Theory of computing, p.83-93, January 1987, New York, New York, United States
	Guy Wolfovitz, The complexity of depth-3 circuits computing symmetric Boolean functions, Information Processing Letters, v.100 n.2, p.41-46, 31 October 2006
	Lane A. Hemaspaandra, SIGACT news complexity theory column 53, ACM SIGACT News, v.37 n.4, December 2006
	Rahul Santhanam, Circuit lower bounds for Merlin-Arthur classes, Proceedings of the thirty-ninth annual ACM symposium on Theory of computing, June 11-13, 2007, San Diego, California, USA
	Ran Raz, Elusive functions and lower bounds for arithmetic circuits, Proceedings of the 40th annual ACM symposium on Theory of computing, May 17-20, 2008, Victoria, British Columbia, Canada
	Benjamin Rossman, On the constant-depth complexity of k-clique, Proceedings of the 40th annual ACM symposium on Theory of computing, May 17-20, 2008, Victoria, British Columbia, Canada
	Goran Gogic , Henry Kautz , Christos Papadimitriou , Bart Selman, The comparative linguistics of knowledge representation, Proceedings of the 14th international joint conference on Artificial intelligence, p.862-869, August 20-25, 1995, Montreal, Quebec, Canada
	Hugo Larochelle , Yoshua Bengio , Jérôme Louradour , Pascal Lamblin, Exploring Strategies for Training Deep Neural Networks, The Journal of Machine Learning Research, 10, p.1-40, June 2009