Compression using efficient multicasting

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Compression using efficient multicasting

Full text

Pdf (1.07 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: 153 - 162

Year of Publication: 2000

ISBN:1-58113-184-4

Authors

Micah Adler	University of Toronto and Department of Computer Science, University of Massachusetts, Amherst, MA
Tom Leighton	Dept. of Mathematics and LCS, MIT and Akamai Technologies, 210 Broadway Street, Cambridge, MA

Sponsor

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 2, Downloads (12 Months): 19, 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/335305.335324 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	M. Adler, New coding techniques for improved bandwidth utilization, Proceedings of the 37th Annual Symposium on Foundations of Computer Science, p.173, October 14-16, 1996
	2	Micah Adler , John W. Byers , Richard M. Karp, Parallel sorting with limited bandwidth, Proceedings of the seventh annual ACM symposium on Parallel algorithms and architectures, p.129-136, June 24-26, 1995, Santa Barbara, California, United States [doi>10.1145/215399.215431]
	3	Micah Adler , Phillip B. Gibbons , Vijaya Ramachandran , Yossi Matias, Modeling parallel bandwidth: local vs. global restrictions, Proceedings of the ninth annual ACM symposium on Parallel algorithms and architectures, p.94-105, June 23-25, 1997, Newport, Rhode Island, United States [doi>10.1145/258492.258502]
	4	Adnan Agbaria , Yosi Ben-Asher , Ilan Newman, Communication-processor tradeoffs in limited resources PRAM, Proceedings of the eleventh annual ACM symposium on Parallel algorithms and architectures, p.74-82, June 27-30, 1999, Saint Malo, France [doi>10.1145/305619.305628]
	5	Alfred V. Aho , John E. Hopcroft, The Design and Analysis of Computer Algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1974
	6	Yossi Azar, Lower bounds for threshold and symmetric functions in parallel computation, SIAM Journal on Computing, v.21 n.2, p.329-338, April 1992 [doi>10.1137/0221024]
	7	Amotz Bar-Noy , Sudipto Guha , Joseph (Seffi) Naor , Baruch Schieber, Multicasting in heterogeneous networks, Proceedings of the thirtieth annual ACM symposium on Theory of computing, p.448-453, May 24-26, 1998, Dallas, Texas, United States [doi>10.1145/276698.276857]
	8	Paul Beame , Faith E. Fich , Rakesh K. Sinha, Separating the power of EREW and CREW PRAMs with small communication width, Information and Computation, v.138 n.1, p.89-99, Oct. 10, 1997 [doi>10.1006/inco.1997.2649]
	9	F. Behrend. On sets of integers containing no three in arithmetic progression. Proc. Nat. Acad. Sci., 23:331-332, 1946.
	10	E. BerIekamp. A construction for partitions avoiding long arithmetic progressions. Canad. Math. Bull., 11:409-414, 1968.
	11	Ashok K. Chandra , Merrick L. Furst , Richard J. Lipton, Multi-party protocols, Proceedings of the fifteenth annual ACM symposium on Theory of computing, p.94-99, December 1983 [doi>10.1145/800061.808737]
	12	David E. Culler , Richard M. Karp , David Patterson , Abhijit Sahay , Eunice E. Santos , Klaus Erik Schauser , Ramesh Subramonian , Thorsten von Eicken, LogP: a practical model of parallel computation, Communications of the ACM, v.39 n.11, p.78-85, Nov. 1996 [doi>10.1145/240455.240477]
	13	R. Dilworth. A decomposition theorem for partially ordered sets. Ann. Math., 51:161-165, 1950.
	14	J. Dongarra Et Al. Document for a standard message-passing interface. In Message Passing Interface Forum, 1993.
	15	F.E. Fich , M. Li , P. Radge , Y. Yesha, On the power of concurrent-write PRAMs with read-only memory, Information and Computation, v.83 n.2, p.234-244, Nov. 1989 [doi>10.1016/0890-5401(89)90059-X]
	16	Faith E. Fich , Prabhakar Ragde , Avi Wigderson, Relations between concurrent-write models of parallel computation, SIAM Journal on Computing, v.17 n.3, p.606-627, June 1988 [doi>10.1137/0217037]
	17	Alexandros V. Gerbessiotis , Constantinos J. Siniolakis, Deterministic sorting and randomized median finding on the BSP model, Proceedings of the eighth annual ACM symposium on Parallel algorithms and architectures, p.223-232, June 24-26, 1996, Padua, Italy [doi>10.1145/237502.237561]
	18	Michael T. Goodrich, Communication-efficient parallel sorting (preliminary version), Proceedings of the twenty-eighth annual ACM symposium on Theory of computing, p.247-256, May 22-24, 1996, Philadelphia, Pennsylvania, United States [doi>10.1145/237814.237870]
	19	R. Graham and V. Rodl. Numbers in Ramsey theory. In Surveys in Combinatorics, (edited by C. Whitehead), LMS Lecture Note Series 123, pages 111-153. Cambridge University Press, 1987.
	20	R. Graham and B. Rothschild. A short proof of van der Waerden's theorem on arithmetic progressions. Proc. Amer. Math. Soc., 42:356-386, 1974.
	21	R. Graham, B. Rothschild, and J. Spencer. Ramsey Theory. John Wiley 2z Sons, 1990.
	22	S. Johnsson, M. Jacquemin, and R. Krawitz. Communication efficient multi-processor FFT. Journal of Computational Physics, 102:381-397, 1992.
	23	M Li , Y Yesha, New lower bounds for parallel computation, Proceedings of the eighteenth annual ACM symposium on Theory of computing, p.177-187, May 28-30, 1986, Berkeley, California, United States [doi>10.1145/12130.12148]
	24	Yishay Mansour , Noam Nisan , Uzi Vishkin, Trade-offs between communication throughput and parallel time, Proceedings of the twenty-sixth annual ACM symposium on Theory of computing, p.372-381, May 23-25, 1994, Montreal, Quebec, Canada [doi>10.1145/195058.195199]
	25	K. Roth. On certain sets of integers. J. London Math. Soc., 28:104-109, 1953.
	26	E. Szemer~di. On sets of integers containing no k elements in arithmetic progression. Acta Arith., 27:199-245, 1975.
	27	Leslie G. Valiant, A bridging model for parallel computation, Communications of the ACM, v.33 n.8, p.103-111, Aug. 1990 [doi>10.1145/79173.79181]
	28	B. van der Waerden. Beweis einer baudetschen vermutung. Nieuw Arch. Wisk., 15:212-216, 1927.
	29	U. Vishkin and A. Wigderson. Trade-offs between depth and width in parallel computation. SIAM Journal of Computing, 14(2):303-314, 1985.