Higher lower bounds on monotone size

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Higher lower bounds on monotone size

Full text

Pdf (1.04 MB)

Source

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

Portland, Oregon, United States

Pages: 378 - 387

Year of Publication: 2000

ISBN:1-58113-184-4

Authors

Danny Harnik	Department of Applied Mathematics and Computer Science, Weizmann Institute, Rehovot, 76100 Israel
Ran Raz	Department of Applied Mathematics and Computer Science, Weizmann Institute, Rehovot, 76100 Israel

Sponsor

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 8, Downloads (12 Months): 26, Citation Count: 2

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

	Aj83	M. AJTAI, E~ Formulae on finite structures, Annals of Pure and Applied Logic 24 (1983), pp. 1-48.
	AlBaIt86	Noga Alon , László Babai , Alon Itai, A fast and simple randomized parallel algorithm for the maximal independent set problem, Journal of Algorithms, v.7 n.4, p.567-583, Dec. 1986 [doi>10.1016/0196-6774(86)90019-2]
	AlBo87	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]
	AmMa96	A. Maruoka, Potential of the approximation method, Proceedings of the 37th Annual Symposium on Foundations of Computer Science, p.431, October 14-16, 1996
	An85	A. ANDREEV, On a method for obtaining lower bounds for the complexity of individual monotone functions, Dolk. Akad. Nauk. $SSR 282(5) (1985), pp. 1033-1037 (in Russian). English translation in: Soviet Math. Dokl. 31(3) (1985), pp. 530-534.
	BeUl97	Christer Berg , Staffan Ulfberg, Symmetric approximation arguments for monotone lower bounds without sunflowers, Computational Complexity, v.8 n.1, p.1-20, June 1999 [doi>10.1007/s000370050017]
	BeUlWi99	C. BERG, S. ULFBERG AND A. WIGDER- SON, Manuscript in preparation.
	BoSi90	Ravi B. Boppana , Michael Sipser, The complexity of finite functions, Handbook of theoretical computer science (vol. A): algorithms and complexity, MIT Press, Cambridge, MA, 1991
	EGLNV92	Guy Even , Oded Goldreich , Michael Luby , Noam Nisan , Boban Veličkovic, Approximations of general independent distributions, Proceedings of the twenty-fourth annual ACM symposium on Theory of computing, p.10-16, May 04-06, 1992, Victoria, British Columbia, Canada [doi>10.1145/129712.129714]
	FuSaSi81	M. FURST, J. SAXE AND M. $IPSER, Parity, circuits and the polynomial time hierarchy, Proc. of the 22th IEEE Symp. on the Foundations of Computer Science (1981), pp. 260-270.
	Ha86	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]
	Ha95	A. Haken, Counting bottlenecks to show monotone P ? NP, Proceedings of the 36th Annual Symposium on Foundations of Computer Science (FOCS'95), p.36, October 23-25, 1995
	Ju97	Stasys Jukna, Finite Limits and Monotone Computations: The Lower Bounds Criterion, Proceedings of the 12th Annual IEEE Conference on Computational Complexity, p.302, June 24-27, 1997
	Pu97	P. PUDLAK, Lower bounds for resolution and cutting planes proofs and monotone computation, The Journal of Symbolic Logic, 62(3) (1997), pp. 981-998.
	Ra85	A. RAZBOROV, Lower bounds on the monotone complexity of some Boolean function, Dolk. Akad. Nauk. SSSR 281(4) (1985), 598-607 (in Russian). English translation in: Soviet Math. Dokl. 31 (1985), 354-357.
	Ra89	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 [doi>10.1145/73007.73023]
	SiTs97	Janos Simon , Shi-Chun Tsai, A Note on the Bottleneck Counting Argument, Proceedings of the 12th Annual IEEE Conference on Computational Complexity, p.297, June 24-27, 1997
	Ya85	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 2

	Kazuo Iwama , Hiroki Morizumi , Jun Tarui, Reductions for monotone Boolean circuits, Theoretical Computer Science, v.408 n.2-3, p.208-212, November, 2008
	Hiroki Morizumi , Jun Tarui, Linear-size log-depth negation-limited inverter for k-tonic binary sequences, Theoretical Computer Science, v.410 n.11, p.1054-1060, March, 2009