Monotone circuits for matching require linear depth

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Monotone circuits for matching require linear depth

Full text

Pdf (430 KB)

Source

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

Baltimore, Maryland, United States

Pages: 287 - 292

Year of Publication: 1990

ISBN:0-89791-361-2

Authors

R. Raz	The Hebrew University
A. Wigderson	The Hebrew University

Sponsor

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

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

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

	Al	N. Alon, Private communication.
	A	A. E. Andreev, "On a Method for Obtaining Lower Bounds on the Complexity of Individual Monotone Functions", Dokl. Ak. Nauk. SSSR, Vol 282, pp. 1033-1037, 1985 (in Russian). English translation in: Soy. Math. Dokl., Vol 31, pp. 530-534, 1985.
	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]
	AG	Miklos Ajtai , Yuri Gurevich, Monotone versus positive, Journal of the ACM (JACM), v.34 n.4, p.1004-1015, Oct. 1987 [doi>10.1145/31846.31852]
	BGH	A. Borodin, 3. von zur Gathen and 3. Hopcroft, "Fast parallel Matrix and GCD Computations", Proceedings o f the 23rd STOC, pp. 65-71, 1982.
	GH	M. Goldmann and 3. Hastad, "A Lower Bound for Monotone Clique using a Communication Game", Manuscript.
	K	M. Karchmer "The Complexity of computation and restricted Machines" Ph.D Thesis, The Hebrew University, 1988.
	KS	B. Kalyanasundaram and G. Snitger "The Probabilistic Communication Complexity of Set Intersection", Proceedings StruCture in Complexity Theorey pp.41-49, 1987.
	KW	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 [doi>10.1145/62212.62265]
	L	L. Lovasz, "Determinants, Matchings and Random Algorithms", in: Proceedings of FCT '89, (ed. L. Budach), Akademie-Verlag, pp. 565-574, 1979.
	R1	A. A. Razborov, "Lower Bounds for the Monotone Complexity of some Boolean Functions", Dokl. Ak. Nauk. SSSR, Vol 281, pp. 798-801, 1985 (in Russian). English translation in Soy. Math. Doki. Vol 31, pp. 354-357, 1985.
	R2	A. A. Razborov, "Lower Bounds on the Monotone Noetwork Complexity of the Logical Permanent", Mat. Zametki, Vol 37, pp. 887-900, 1985 (in Russian). English translation in : Math. Notes of the Academy of Sciences of USSR, Vol 37, pp. 485-493, 1985.
	R3	A. A. Razborov, "On the Distributional Complexity of Disjointness", Manuscript.
	RW	R. Raz and A. Wigderson, "Probabilistic Communication Complexity of Boolean Relations", Proc. of the 30th FOCS, to appear, 1989.
	T	E. Tardos, "The Gap between Monotone and Non-monotone Circuit Complexity is Exponential", Combinatorica, Vol 8, pp. 141-142, 1988.
	W	Ingo Wegener, The complexity of Boolean functions, John Wiley & Sons, Inc., New York, NY, 1987
	Y	Andrew Chi-Chih Yao, Some complexity questions related to distributive computing(Preliminary Report), Proceedings of the eleventh annual ACM symposium on Theory of computing, p.209-213, April 30-May 02, 1979, Atlanta, Georgia, United States [doi>10.1145/800135.804414]

CITED BY 6

	J. Hromkovic , G. Schnitger, Nondeterministic communication with a limited number of advice bits, Proceedings of the twenty-eighth annual ACM symposium on Theory of computing, p.551-560, May 22-24, 1996, Philadelphia, Pennsylvania, United States
	Maria Bonet , Toniann Pitassi , Ran Raz, Lower bounds for cutting planes proofs with small coefficients, Proceedings of the twenty-seventh annual ACM symposium on Theory of computing, p.575-584, May 29-June 01, 1995, Las Vegas, Nevada, United States
	Paul Beame , Joan Lawry, Randomized versus nondeterministic communication complexity, Proceedings of the twenty-fourth annual ACM symposium on Theory of computing, p.188-199, May 04-06, 1992, Victoria, British Columbia, Canada
	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
	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
	Carsten Damm , Matthias Krause , Christoph Meinel , Stephan Waack, On relations between counting communication complexity classes, Journal of Computer and System Sciences, v.69 n.2, p.259-280, September 2004