Randomness-optimal unique element isolation, with applications to perfect matching and related problems

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Randomness-optimal unique element isolation, with applications to perfect matching and related problems

Full text

Pdf (972 KB)

Source

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

San Diego, California, United States

Pages: 458 - 467

Year of Publication: 1993

ISBN:0-89791-591-7

Authors

Suresh Chari
Pankaj Rohatgi
Aravind Srinivasan

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): 15, Citation Count: 2

Additional Information:

references cited by index terms collaborative colleagues peer to peer

Tools and Actions:	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/167088.167213 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.

	Adl78	L. Adleman. Two theorems on random polynomial time. In Proceedings of the IEEE Symposium on Foundations of Computer Science, pages 75-83, 1978.
	CGM92	P. M. Camerini , G. Galbiati , F. Maffioli, Random pseudo-polynomial algorithms for exact matroid problems, Journal of Algorithms, v.13 n.2, p.258-273, June, 1992 [doi>10.1016/0196-6774(92)90018-8]
	CG89	B. Chor , O. Goldreich, On the power of two-point based sampling, Journal of Complexity, v.5 n.1, p.96-106, March 1989 [doi>10.1016/0885-064X(89)90015-0]
	CH90	J-Y. Cai and L. Hemachandra. On the Power of Parity Polynomial Time. Math. Systems Theory, 23(2):95-106, 1990.
	Csa76	L. Csanky. Fast parallel matrix inversion algorithms. SIAM J. Comput., 5:618-623, 1976.
	CW79	J.L. Carter and M. N. Wegman. Universal classes of hash functions. Journal of Computer and System Sciences, 18:143- 154, 1979.
	dB51	N. de Bruijn. On the number of positive integers _< x and free of prime factors > y. Proc. Kon. Ned. Akad. Wet.(Indag. Math. 13), A54:50-60, 1951.
	DK86	Elias Dahlhaus , Marek Karpinski, The Matching Problem for Strongly Chordal Graphs is in $NC$, University of Bonn, 1986
	GK87	Dima Yu Grigoriev , Marek Karpinski , Michael F. Singer, Fast parallel algorithms for sparse multivariate polynomial interpolation over finite fields, SIAM Journal on Computing, v.19 n.6, p.1059-1063, Dec. 1990 [doi>10.1137/0219073]
	GPST92	Andrew V. Goldberg , Serge A. Plotkin , David B. Shmoys , Éva Tardos, Using interior-point methods for fast parallel algorithms for bipartite matching and related problems, SIAM Journal on Computing, v.21 n.1, p.140-150, Feb. 1992 [doi>10.1137/0221011]
	GPV93	Andrew V. Goldberg , Serge A. Plotkin , Pravin M. Vaidya, Sublinear-time parallel algorithms for matching and related problems, Journal of Algorithms, v.14 n.2, p.180-213, March 1993 [doi>10.1006/jagm.1993.1009 ]
	Gro92	L.K. Grover. Fast parallel algorithms for bipartite matching. In Proceedings o/ the Integer Programming and Combinatorial Optimization Conference, pages 367- 384, 1992.
	Kar86	H. J. Karloff, A Las Vegas RNC algorithm for maximum matching, Combinatorica, v.6 n.4, p.387-391, 1986 [doi>10.1007/BF02579264]
	Kas67	P.W. Kastelyn. Graph theory and crystal physics. In F. Harary, editor, Graph Theory and Theoretical Physics, pages 43-110. Academic Press, New York, 1967.
	KSTT89	J. KSbler, U. SchSning, S. Toda, and J. Torah. Turing machines with few accepting computations and low sets for PP. In Proceedings of the IEEE Symposium on Structure in Complexity Theory, pages 208-215, 1989.
	KUW86	R M Karp , E Upfal , A Wigderson, Constructing a perfect matching is in random NC, Combinatorica, v.6 n.1, p.35-48, 1986 [doi>10.1007/BF02579407]
	KVV85	Dexter Kozen , Umesh V. Vazirani , Vijay V. Vazirani, NC Algorithms for Comparability Graphs, Interval Gaphs, and Testing for Unique Perfect Matching, Proceedings of the Fifth Conference on Foundations of Software Technology and Theoretical Computer Science, p.496-503, December 16-18, 1985
	LP86	L. Lov,4sz and M. Plummer. Matching Theory. North-Holland, Amsterdam, 1986.
	MN89	G.L. Miller and J. Naor. Flow in planar graphs with multiple sources and sinks. In Proceedings of the IEEE Symposium on Foundations of Computer Science, pages 112-117, 1989.
	MVV87	K. Mulmuley , U. V. Vazirani , V. V. Vazirani, Matching is as easy as matrix inversion, Combinatorica, v.7 n.1, p.105-113, Jan. 1987 [doi>10.1007/BF02579206]
	NSV92	H. Narayanan , Huzur Saran , Vijay V. Vazirani, Randomized parallel algorithms for matroid union and intersection, with applications to arboresences and edge-disjoint spanning trees, Proceedings of the third annual ACM-SIAM symposium on Discrete algorithms, p.357-366, September 1992, Orlando, Florida, United States
	PY82	Christos H. Papadimitriou , Mihalis Yannakakis, The complexity of restricted spanning tree problems, Journal of the ACM (JACM), v.29 n.2, p.285-309, April 1982 [doi>10.1145/322307.322309]
	Rab82	M.O. Rabin. N-process mutual exclusion with bounded waiting by 4log2 N-valued shared variable. Journal of Computer and System Sciences, 25(1):66-75, 1982.
	Tar91	Jun Tarui, Randomized polynomials, threshold circuits, and the polynomial hierarchy, Proceedings of the 8th annual symposium on Theoretical aspects of computer science, p.238-250, February 1991, Hamburg, Germany
	Thr93	W. Thrash. A Note on the Least Common Multiples of Dense Sets of Integers. Technical Report #93-02-04, Department of Computer Science & Engineering, University of Washington, Seattle, Feb. 199.3.
	Tiw87	P. Tiwari Parallel algorithms for instances of linear matroid parity with small number of solutions. Technical Report RC 127(;6, IBM T.J. Watson Research Center, May 1987.
	Tod91	Seinosuke Toda, PP is as hard as the polynomial-time hierarchy, SIAM Journal on Computing, v.20 n.5, p.865-877, Oct. 1991 [doi>10.1137/0220053]
	Tom91	M. Tompa. Lecture notes on probabilistic algorithms and pseudorandom generators. Technical Report #91-07-05, Department of Computer Science & Engineering, University of Washington, Seattle, July 1991.
	Vai90	P.M. Vaidya. Reducing the parallel complexity of certain linear programming problems, in Proceedings of the IEEE Symposium on Foundations o# Computer Science, pages 583-589, 1990.
	Vaz89	Vijay V. Vazirani, NC algorithms for computing the number of perfect matchings in K3,3-free graph and related problems, Information and Computation, v.80 n.2, p.152-164, Feb. 1989 [doi>10.1016/0890-5401(89)90017-5]
	VV86	L. G. Valiant , V. V. Vazirani, NP is as easy as detecting unique solutions, Theoretical Computer Science, v.47 n.1, p.85-93, Nov. 1986

CITED BY 2

	Ran Canetti , Eyal Kushilevitz , Rafail Ostrovsky , Adi Rosén, Randomness vs. fault-tolerance, Proceedings of the sixteenth annual ACM symposium on Principles of distributed computing, p.35-44, August 21-24, 1997, Santa Barbara, California, United States
	Rajiv Gupta , Scott A. Smolka , Shaji Bhaskar, On randomization in sequential and distributed algorithms, ACM Computing Surveys (CSUR), v.26 n.1, p.7-86, March 1994