On data structures and asymmetric communication complexity

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

On data structures and asymmetric communication complexity

Full text

Pdf (938 KB)

Source

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

Las Vegas, Nevada, United States

Pages: 103 - 111

Year of Publication: 1995

ISBN:0-89791-718-9

Authors

Peter Bro Miltersen	Dept. of CS, University of Toronto
Noam Nisan	Dept. of CS, Hebrew University, Jerusalem
Shmuel Safra	Hebrew U and Weizmann Institute and BRICS at the University of Aarhus
Avi Wigderson	Dept. of CS, Hebrew University, Jerusalem

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): 17, Citation Count: 10

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

	Ajt88	M. Ajtai. A lower bound for finding predecessors in Yao's cell probe model. Combinatorics, 8:235- 247, 1988.
	BF94	P. Beame, F. Fich, personal communication.
	DGS84	Pavol Duris , Zvi Galil , Georg Schnitger, Lower bounds on communication complexity, Proceedings of the sixteenth annual ACM symposium on Theory of computing, p.81-91, December 1984 [doi>10.1145/800057.808668]
	FKS84	Michael L. Fredman , János Komlós , Endre Szemerédi, Storing a Sparse Table with 0(1) Worst Case Access Time, Journal of the ACM (JACM), v.31 n.3, p.538-544, July 1984 [doi>10.1145/828.1884]
	HR88	Bernd Halstenberg , Rudiger Reischuk, On different modes of communication, Proceedings of the twentieth annual ACM symposium on Theory of computing, p.162-172, May 02-04, 1988, Chicago, Illinois, United States [doi>10.1145/62212.62226]
	KW90	M. Karchmer and A. Wigderson. Monotone cir-cuits for connectivity require super-logarithmic depth. SIAM Journa~ on Discrete Mathematics, 3, 1990.
	KPPY84	Maria Klawe , Wolfgang J. Paul , Nicholas Pippenger , Mihalis Yannakakis, On monotone formulae with restricted depth, Proceedings of the sixteenth annual ACM symposium on Theory of computing, p.480-487, December 1984 [doi>10.1145/800057.808717]
	MS82	Kurt Mehlhorn , Erik M. Schmidt, Las Vegas is better than determinism in VLSI and distributed computing (Extended Abstract), Proceedings of the fourteenth annual ACM symposium on Theory of computing, p.330-337, May 05-07, 1982, San Francisco, California, United States [doi>10.1145/800070.802208]
	Mi193	Peter Bro Miltersen, The Bit Probe Complexity Measure Revisited, Proceedings of the 10th Annual Symposium on Theoretical Aspects of Computer Science, p.662-671, February 25-27, 1993
	Mi194	Peter Bro Miltersen, Lower bounds for union-split-find related problems on random access machines, Proceedings of the twenty-sixth annual ACM symposium on Theory of computing, p.625-634, May 23-25, 1994, Montreal, Quebec, Canada [doi>10.1145/195058.195415]
	Mi195	Peter Bro Miltersen, On the cell probe complexity of polynomial evaluation, Theoretical Computer Science, v.143 n.1, p.167-174, May 29, 1995
	Ni93	N. Nisan. The communication complexity of threshold gates. In Proc. of "Combinatorics, Paul Erdos is Eighty", (1993) 301-315.
	NW93	Noam Nisan , Avi Wigderson, Rounds in communication complexity revisited, SIAM Journal on Computing, v.22 n.1, p.211-219, Feb. 1993 [doi>10.1137/0222016]
	Smi88	D.V. Smirnov, Shannon's information methods fc.v lozu.r bounds fo. p.obabilisti. .ommqni.cztiorz complexity. Master's Thesis, Moscow University, 1988.
	Weg87	Ingo Wegener, The complexity of Boolean functions, John Wiley & Sons, Inc., New York, NY, 1987
	Wi183	D.E. Willard. Log-logarithmic worst case range queries are possible in space O(n). Inform. Pro-cess. Lett., 17:81-84, 1983.
	Xia92	Bing Xiao, New bounds in cell probe model, University of California at San Diego, La Jolla, CA, 1992
	Yao77	A. C. Yao. Probabilistic computations: Toward a unified measure of complexity. In Proc. 18th IEEE Symposium on Foundations of Computer Science (FOCS) (1977) 222-227.
	Yao79	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]
	Yao81	Andrew Chi-Chih Yao, Should Tables Be Sorted?, Journal of the ACM (JACM), v.28 n.3, p.615-628, July 1981 [doi>10.1145/322261.322274]
	Yao83	A. C. Yao. Lower bounds by probabilistic argu-ments. In Proc. 2Jth IEEE Symposium on Foun-dations of Computer Science (FOCS) (1983) 420-428.

CITED BY 10

	Amit Chakrabarti , T. S. Jayram , Mihai Pǎtraşcu, Tight lower bounds for selection in randomly ordered streams, Proceedings of the nineteenth annual ACM-SIAM symposium on Discrete algorithms, p.720-729, January 20-22, 2008, San Francisco, California
	Thore Husfeldt , Theis Rauhe , Søren Skyum, Lower bounds for dynamic transitive closure, planar point location, and parantheses matching, Nordic Journal of Computing, v.3 n.4, p.323-336, Winter 1996
	Ilan Kremer , Noam Nisan , Dana Ron, On randomized one-round communication complexity, Proceedings of the twenty-seventh annual ACM symposium on Theory of computing, p.596-605, May 29-June 01, 1995, Las Vegas, Nevada, United States
	Hartmut Klauck , Ashwin Nayak , Amnon Ta-Shma , David Zuckerman, Interaction in quantum communication and the complexity of set disjointness, Proceedings of the thirty-third annual ACM symposium on Theory of computing, p.124-133, July 2001, Hersonissos, Greece
	Mikkel Thorup, On RAM priority queues, Proceedings of the seventh annual ACM-SIAM symposium on Discrete algorithms, p.59-67, January 28-30, 1996, Atlanta, Georgia, United States
	Amit Chakrabarti , Bernard Chazelle , Benjamin Gum , Alexey Lvov, A lower bound on the complexity of approximate nearest-neighbor searching on the Hamming cube, Proceedings of the thirty-first annual ACM symposium on Theory of computing, p.305-311, May 01-04, 1999, Atlanta, Georgia, United States
	Joseph M. Hellerstein , Elias Koutsoupias , Daniel P. Miranker , Christos H. Papadimitriou , Vasilis Samoladas, On a model of indexability and its bounds for range queries, Journal of the ACM (JACM), v.49 n.1, p.35-55, January 2002
	Omer Barkol , Yuval Rabani, Tighter lower bounds for nearest neighbor search and related problems in the cell probe model, Journal of Computer and System Sciences, v.64 n.4, p.873-896, June 2002
	Omer Barkol , Yuval Rabani, Tighter bounds for nearest neighbor search and related problems in the cell probe model, Proceedings of the thirty-second annual ACM symposium on Theory of computing, p.388-396, May 21-23, 2000, Portland, Oregon, United States
	Allan Borodin , Rafail Ostrovsky , Yuval Rabani, Lower bounds for high dimensional nearest neighbor search and related problems, Proceedings of the thirty-first annual ACM symposium on Theory of computing, p.312-321, May 01-04, 1999, Atlanta, Georgia, United States