Improved algorithms via approximations of probability distributions (extended abstract)

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Improved algorithms via approximations of probability distributions (extended abstract)

Full text

Pdf (890 KB)

Source

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

Montreal, Quebec, Canada

Pages: 584 - 592

Year of Publication: 1994

ISBN:0-89791-663-8

Authors

Suresh Chari	Dept. of Computer Science, Cornell University, Ithaca NY
Pankaj Rohatgi	Thompson Consumer Electronics, Los Angeles, CA
Aravind Srinivasan	DIMACS Center, Rutgers University, Piscataway, NJ, and School of Mathematics, The Institute for Advanced Study, Princeton, NJ

Sponsor

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 1, Downloads (12 Months): 9, Citation Count: 1

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

	1	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]
	2	N. Alon, J. Bruck, J. Naor, M. Naor, and R. Roth. Construction of asymptotically good, low-rate errorcorrecting codes through pseudo-random graphs. IEEE Transactions on In}ormation Theory, 38:509- 516, 1992.
	3	N. Alon, O. Goldreich, J. Hkstad, and R. Peralta. Simple constructions of almost k-wise independent random variables. Random Structures and Algorithms, 3(3):289-303, 1992.
	4	N. Alon and M. Naor. Derandomization, witnessses for Boolean matrix multiplication and construction of perfect hash functions. Manuscript, 1992.
	5	Y. Azar, R. Motwani, and J. Naor. Approximating arbitrary probability distributions using small sample spaces. Manuscript, 1990.
	6	J. L. Bentley and D. Wood. An optimal worst-case algorithm for reporting intersections of rectangles. IEEE Trans. Comput., 29:571-577, 1980.
	7	Bonnie Berger, Simulating (logcn)-wise independence in NC, Journal of the ACM (JACM), v.38 n.4, p.1026-1046, Oct. 1991 [doi>10.1145/115234.115347]
	8	Bonnie Berger , John Rompel , Peter W. Shor, Efficient NC algorithms for set cover with applications to learning and geometry, Proceedings of the 30th IEEE symposium on Foundations of computer science, p.454-477, December 1994, Research Triangle Park, North Carolina, United States
	9	Bonnie Berger , Peter W. Shor, Approximation alogorithms for the maximum acyclic subgraph problem, Proceedings of the first annual ACM-SIAM symposium on Discrete algorithms, p.236-243, January 22-24, 1990, San Francisco, California, United States
	10	B. Chazelle and 3. Friedman. A deterministic view of random sampling and its use in geometry. Combinatorica, 10(3):229-249, 1990.
	11	Bernard Chazelle , Jiří Matoušek, On linear-time deterministic algorithms for optimization problems in fixed dimension, Proceedings of the fourth annual ACM-SIAM Symposium on Discrete algorithms, p.281-290, January 25-27, 1993, Austin, Texas, United States
	12	P. Erd#s and D. Kleitman. On coloring graphs to maximize the proportion of multicolored k-edges. Journal of Combinatorial Theory, 5(2):164-169, 1968.
	13	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]
	14	Richard M. Karp , Avi Wigderson, A fast parallel algorithm for the maximal independent set problem, Journal of the ACM (JACM), v.32 n.4, p.762-773, Oct. 1985 [doi>10.1145/4221.4226]
	15	Pierre Kelsen, On the parallel complexity of computing a maximal independent set in a hypergraph, Proceedings of the twenty-fourth annual ACM symposium on Theory of computing, p.339-350, May 04-06, 1992, Victoria, British Columbia, Canada [doi>10.1145/129712.129745]
	16	R. Lidl and H. Niederreiter. Finite Fields. Addison- Wesley, 1983. ~
	17	Michael Luby, A simple parallel algorithm for the maximal independent set problem, SIAM Journal on Computing, v.15 n.4, p.1036-1055, Nov. 1986 [doi>10.1137/0215074]
	18	M. Luby. Removing randomness in parallel computation without a processor penalty, in Proc. IEEE Symposium on Foundations of Computer Science, pages 162-173, 1988.
	19	Michael Luby , Noam Nisan, A parallel approximation algorithm for positive linear programming, Proceedings of the twenty-fifth annual ACM symposium on Theory of computing, p.448-457, May 16-18, 1993, San Diego, California, United States [doi>10.1145/167088.167211]
	20	Rajeev Motwani , Joseph Seffi Naor , Moni Naor, The probabilistic method yields deterministic parallel algorithms, Proceedings of the 30th IEEE symposium on Foundations of computer science, p.478-516, December 1994, Research Triangle Park, North Carolina, United States
	21	J. Naor , M. Naor, Small-bias probability spaces: efficient constructions and applications, Proceedings of the twenty-second annual ACM symposium on Theory of computing, p.213-223, May 13-17, 1990, Baltimore, Maryland, United States [doi>10.1145/100216.100244]
	22	N. Nisan, E. Szemer6di, and A. Wigderson. Undirected connectivity in O(log1'# n) space. In Proc. IEEE Symposium on Foundations of Computer Science, pages 24-29, 1992.
	23	Alessandro Panconesi , Aravind Srinivasan, Improved distributed algorithms for coloring and network decomposition problems, Proceedings of the twenty-fourth annual ACM symposium on Theory of computing, p.581-592, May 04-06, 1992, Victoria, British Columbia, Canada [doi>10.1145/129712.129769]
	24	Franco P. Preparata , Michael I. Shamos, Computational geometry: an introduction, Springer-Verlag New York, Inc., New York, NY, 1985
	25	Prabhakar Raghavan, Probabilistic construction of deterministic algorithms: approximating packing integer programs, Journal of Computer and System Sciences, v.37 n.2, p.130-143, October 1988 [doi>10.1016/0022-0000(88)90003-7]
	26	S. Rajagopalan and V. V. Vazirani. Primal-dual RNC approximation algorithms for (multi)-set (multi)- cover and covering integer programs. In Proc. 1EEE Symposium on Foundations of Computer Science, pages 322-331, 1993.
	27	Miklos Santha , Umesh V Vazirani, Generating quasi-random sequences from semi-random sources, Journal of Computer and System Sciences, v.33 n.1, p.75-87, Aug. 1986 [doi>10.1016/0022-0000(86)90044-9]
	28	Jeanette P. Schmidt , Alan Siegel , Aravind Srinivasan, Chernoff-Hoeffding Bounds for Applications with Limited Independence, SIAM Journal on Discrete Mathematics, v.8 n.2, p.223-250, May 1995 [doi>10.1137/S089548019223872X]
	29	J Spencer, Balancing vectors in the max norm, Combinatorica, v.6 n.1, p.55-65, 1986 [doi>10.1007/BF02579409]
	30	J. Spencer. Ten Lectures on the Probabilistic Method. SIAM, Philadelphia, 1987.