Algebraic methods in the theory of lower bounds for Boolean circuit complexity

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Algebraic methods in the theory of lower bounds for Boolean circuit complexity

Full text

Pdf (417 KB)

Source

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

New York, New York, United States

Pages: 77 - 82

Year of Publication: 1987

ISBN:0-89791-221-7

Author

R. Smolensky

Department of Mathematics, University of California, Berkeley

Sponsor

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 10, Downloads (12 Months): 100, Citation Count: 43

Additional Information:

abstract 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/28395.28404 What is a DOI?

ABSTRACT

We use algebraic methods to get lower bounds for complexity of different functions based on constant depth unbounded fan-in circuits with the given set of basic operations. In particular, we prove that depth k circuits with gates NOT, OR and MODp where p is a prime require Exp(&Ogr;(n1/2k)) gates to calculate MODr functions for any r ≠ pm. This statement contains as special cases Yao's PARITY result [ Ya 85 ] and Razborov's new MAJORITY result [Ra 86] (MODm gate is an oracle which outputs zero, if the number of ones is divisible by m).

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 83	M. Ajtai, "E' formulae on finite structures", Annals of Pure and Applied Logic.
	Ba 86	D A Barrington, Bounded-width polynomial-size branching programs recognize exactly those languages in NC¹, Proceedings of the eighteenth annual ACM symposium on Theory of computing, p.1-5, May 28-30, 1986, Berkeley, California, United States [doi>10.1145/12130.12131]
	Ba 2	D.A. Barrington, "A note on the theorem of Razborov" (unpublished)
	Ca 86	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]
	FKPS 83	A. Fagin, M.M. K!awe, N.J. Pippenger, ~nd L. Stockmeyer, "Bounded depth, polynomial-si::e circuits fi)r symmetric functions", IBM Report RJ 4040 (October 1983), IBM Research Laboratory, San Jose.
	FSS 81	M. Furst, J.B. Saxe, and M. Sipper, "Parity, circuits and the polynomial time hierarchy", Proc. 22nd IEEE FOCS, 1981, 260-270.
	Ha 86	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]
	Ra 86	A.A. Razborov, "Lower bounds for the size of cilxuits of bounded depth with basis AND, XOR", preprint (in Russia~). To appear in C'Ma~em. zam."
	Ya 85	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 43

	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
	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
	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
	Noam Nisan , Mario Szegedy, On the degree of Boolean functions as real polynomials, Proceedings of the twenty-fourth annual ACM symposium on Theory of computing, p.462-467, May 04-06, 1992, Victoria, British Columbia, Canada
	A. A. Razborov, On the method of approximations, Proceedings of the twenty-first annual ACM symposium on Theory of computing, p.167-176, May 14-17, 1989, Seattle, Washington, United States
	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
	Matthias Krause , Pavel Pudlák, On the computational power of depth 2 circuits with threshold and modulo gates, Proceedings of the twenty-sixth annual ACM symposium on Theory of computing, p.48-57, May 23-25, 1994, Montreal, Quebec, Canada
	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
	Nathan Linial , Yishay Mansour , Noam Nisan, Constant depth circuits, Fourier transform, and learnability, Journal of the ACM (JACM), v.40 n.3, p.607-620, July 1993
	Dima Grigoriev , Marek Karpinski, An exponential lower bound for depth 3 arithmetic circuits, Proceedings of the thirtieth annual ACM symposium on Theory of computing, p.577-582, May 24-26, 1998, Dallas, Texas, United States
	Alexander A. Razborov , Steven Rudich, Natural proofs, Proceedings of the twenty-sixth annual ACM symposium on Theory of computing, p.204-213, May 23-25, 1994, Montreal, Quebec, Canada
	Alexis Maciel , Toniann Pitassi, On ACC0[pk] Frege proofs, Proceedings of the twenty-ninth annual ACM symposium on Theory of computing, p.720-729, May 04-06, 1997, El Paso, Texas, United States
	Michael Sipser, The history and status of the P versus NP question, Proceedings of the twenty-fourth annual ACM symposium on Theory of computing, p.603-618, May 04-06, 1992, Victoria, British Columbia, Canada
	James Aspnes , Richard Beigel , Merrick Furst , Steven Rudich, The expressive power of voting polynomials, Proceedings of the twenty-third annual ACM symposium on Theory of computing, p.402-409, May 05-08, 1991, New Orleans, Louisiana, 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
	Ramamohan Paturi, On the degree of polynomials that approximate symmetric Boolean functions (preliminary version), Proceedings of the twenty-fourth annual ACM symposium on Theory of computing, p.468-474, May 04-06, 1992, Victoria, British Columbia, Canada
	Sam Buss , Dima Grigoriev , Russell Impagliazzo , Toniann Pitassi, Linear gaps between degrees for the polynomial calculus modulo distinct primes, Proceedings of the thirty-first annual ACM symposium on Theory of computing, p.547-556, May 01-04, 1999, Atlanta, Georgia, United States
	Amir Shpilka, Affine projections of symmetric polynomials, Journal of Computer and System Sciences, v.65 n.4, p.639-659, December 2002
	Matthias Krause , Stefan Lucks, Pseudorandom functions in TC⁰ and cryptographic limitations to proving lower bounds, Computational Complexity, v.10 n.4, p.297-313, May 2002
	M. Dietzfelbinger , M. Kutylowski , R. Reischuk, Exact time bounds for computing boolean functions on PRAMs without simultaneous writes, Proceedings of the second annual ACM symposium on Parallel algorithms and architectures, p.125-135, July 02-06, 1990, Island of Crete, Greece
	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
	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
	Frederic Green, The correlation between parity and quadratic polynomials mod 3, Journal of Computer and System Sciences, v.69 n.1, p.28-44, August 2004
	Eric Allender , Anna Bernasconi , Carsten Damm , Joachim von Zur Gathen , Michael Saks , Igor Shparlinski, Complexity of some arithmetic problems for binary polynomials, Computational Complexity, v.12 n.1/2, p.23-25, July 2004
	Pascal Tesson , Denis Thérien, The computing power of programs over finite monoids, Journal of Automata, Languages and Combinatorics, v.7 n.2, p.247-258, November 2001
	Farid Ablayev , Aida Gainutdinova , Marek Karpinski , Cristopher Moore , Christopher Pollett, On the computational power of probabilistic and quantum branching program, Information and Computation, v.203 n.2, p.145-162, December 15, 2005
	Nayantara Bhatnagar , Parikshit Gopalan , Richard J. Lipton, Symmetric polynomials over Zm and simultaneous communication protocols, Journal of Computer and System Sciences, v.72 n.2, p.252-285, March 2006
	Holger Spakowski , Rahul Tripathi, LWPP and WPP are not uniformly gap-definable, Journal of Computer and System Sciences, v.72 n.4, p.660-689, June 2006
	Lane A. Hemaspaandra, SIGACT news complexity theory column 53, ACM SIGACT News, v.37 n.4, December 2006
	Debajyoti Bera , Frederic Green , Steven Homer, Small depth quantum circuits, ACM SIGACT News, v.38 n.2, June 2007
	Yuval Ishai , Eyal Kushilevitz , Rafail Ostrovsky , Amit Sahai, Zero-knowledge from secure multiparty computation, Proceedings of the thirty-ninth annual ACM symposium on Theory of computing, June 11-13, 2007, San Diego, California, USA
	S. Jukna, On Graph Complexity, Combinatorics, Probability and Computing, v.15 n.6, p.855-876, November 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
	Omer Barkol , Yuval Ishai , Enav Weinreb, Communication in the presence of replication, Proceedings of the 40th annual ACM symposium on Theory of computing, May 17-20, 2008, Victoria, British Columbia, Canada
	Ronen Shaltiel , Emanuele Viola, Hardness amplification proofs require majority, Proceedings of the 40th annual ACM symposium on Theory of computing, May 17-20, 2008, Victoria, British Columbia, Canada
	Scott Aaronson , Avi Wigderson, Algebrization: A New Barrier in Complexity Theory, ACM Transactions on Computation Theory (TOCT), v.1 n.1, p.1-54, February 2009
	Emanuele Viola, Guest Column: correlation bounds for polynomials over {0 1}, ACM SIGACT News, v.40 n.1, March 2009
	Saugata Basu , Nayantara Bhatnagar , Parikshit Gopalan , Richard J. Lipton, Polynomials that Sign Represent Parity and Descartes' Rule of Signs, Computational Complexity, v.17 n.3, p.377-406, October 2008
	R. Ryan Williams, Time-Space Tradeoffs for Counting NP Solutions Modulo Integers, Computational Complexity, v.17 n.2, p.179-219, May 2008
	Phokion G. Kolaitis , Swastik Kopparty, Random graphs and the parity quantifier, Proceedings of the 41st annual ACM symposium on Theory of computing, May 31-June 02, 2009, Bethesda, MD, USA