On the method of approximations

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

On the method of approximations

Full text

Pdf (866 KB)

Source

Annual ACM Symposium on Theory of Computing archive
Proceedings of the twenty-first annual ACM symposium on Theory of computing table of contents

Seattle, Washington, United States

Pages: 167 - 176

Year of Publication: 1989

ISBN:0-89791-307-8

Author

A. A. Razborov

Steldov Mathematical Institute, 117966, MOSCOW, GSP-1, Vavilova, 42, USSR

Sponsor

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 3, Downloads (12 Months): 22, Citation Count: 7

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

	AB87	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]
	AE85	Andreev A. E. On a method for obtaining lower bounds for the complexity of individual monotone functions. Doklady Akademii Nauk, 282(5)'1033-1037, 1985. English translation in: Soviet Mathematics Doklady 31:3, 530-534.
	AKS83	M. Ajtai , J. Komlós , E. Szemerédi, An 0(n log n) sorting network, Proceedings of the fifteenth annual ACM symposium on Theory of computing, p.1-9, December 1983 [doi>10.1145/800061.808726]
	And87	A. E. Andreev. On one method of obtaining constructive lower bounds for the monotone circuit size. Algebra and Logics, 26(1)'3-26, 1987.
	BS88	R. Boppana and M. Sipser. Complexity of finite functions. Cambridge, USA, 1988. preprint.
	Pat86	M. Paterson. Bounded depth circuits over {&, $}. Warwick, Britain, 1986. preprint.
	Raz85a	A. A. Razborov. A lower bound on the monotone network complexity of the logical permanent. Mathematicheskie gametki, 37(6)'887-900, 1985. English translation in: 2(athematical Notes of the Academy of Sciences of the USSR 37:6,485-493.
	Raz85b	A. A. Razborov. Lower bounds on the monotone complexity of some boolean functions. Doklady Akademii Naul:, 281(4) 798- 801, 1985. English translation in: Soviet Mathematics Doklady 31,354- 357.
	Raz86	A.A. Razborov. Lower bounds for the monotone complexity of boolean functions. In Proceedings of the International Congress of Mathematicians, pages 1478-1487, Berkeley, California, 1986.
	Raz87	A.A. Razborov. Lower bounds on the size of bounded depth networks over a complete basis with logical addition. Mathematicheskie Zametki, 41 (4)'598-607, 1987. English translation in: Mathematical Notes of the Academy of Sciences of the USSR 41:4, 333-338.
	Smo87	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 [doi>10.1145/28395.28404]
	Tar89	Eva Tardos. The gap between monotone and non-monotone circuit complexity is exponenial. 1989. to appear in Combinatorica.

CITED BY 7

	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
	László Babai , Anna Gál , János Kollár , Lajos Rónyai , Tibor Szabó , Avi Wigderson, Extremal bipartite graphs and superpolynomial lower bounds for monotone span programs, Proceedings of the twenty-eighth annual ACM symposium on Theory of computing, p.603-611, May 22-24, 1996, Philadelphia, Pennsylvania, 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
	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
	Anna Gál, A characterization of span program size and improved lower bounds for monotone span programs, Proceedings of the thirtieth annual ACM symposium on Theory of computing, p.429-437, May 24-26, 1998, Dallas, Texas, United States
	Kazuyuki Amano , Akira Maruoka , Jun Tarui, On the negation-limited circuit complexity of merging, Discrete Applied Mathematics, v.126 n.1, p.3-8, March 2003
	Anna Gál, A characterization of span program size and improved lower bounds for monotone span programs, Computational Complexity, v.10 n.4, p.277-296, May 2002