Lower bounds for union-split-find related problems on random access machines

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Lower bounds for union-split-find related problems on random access machines

Full text

Pdf (881 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: 625 - 634

Year of Publication: 1994

ISBN:0-89791-663-8

Author

Peter Bro Miltersen

Aarhus University and University of Warwick, Department of Computer Science, Coventry, CV4 7AL, U.K.

Sponsor

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 5, Downloads (12 Months): 26, Citation Count: 22

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.195415 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	A. Aggarwal , J. S. Vitter, The I/O complexity of sorting and related problems, 14th International Colloquium on Automata, languages and programming, p.467-478, July 1987, Karlsruhe, Germany
	2	M. Ajtai, A lower bound for finding predecessors in Yao's cell probe model, Combinatorica s (19ss)235-247.
	3	M. Ajtai, Persona/communication.
	4	M. Ajtai, M. Fredman, J. Koml6s, Hash functions for priority queues, in: Proc. 24th Ann. IEEE Syrup. on Foundations of Computer Science (1983) 299-303.
	5	D. Anghin, L.G. Valiant, Fast Probabilistic Algorithms for Hamiltonian Circuits and Matchings, J. Comput. System Sci. 18 (1979) 155-193.
	6	Bernard Chazelle, Lower bounds for orthogonal range searching: part II. The arithmetic model, Journal of the ACM (JACM), v.37 n.3, p.439-463, July 1990 [doi>10.1145/79147.79149]
	7	Peter Elias , Richard A. Flower, The Complexity of Some Simple Retrieval Problems, Journal of the ACM (JACM), v.22 n.3, p.367-379, July 1975 [doi>10.1145/321892.321899]
	8	G.S. Frandsen, P.B. Miltersen, S. Skyum, Dynamic word problems, in: Proc. 34th Ann. IEEE Syrup. on Foundations of Computer Science (1993) 470-479.
	9	M.L. Fredman, Observations on the complexity of generating quasi-Gray codes, SIAM J. Comput. 7 (1978) 134-146.
	10	Michael L. Fredman, The Complexity of Maintaining an Array and Computing Its Partial Sums, Journal of the ACM (JACM), v.29 n.1, p.250-260, Jan. 1982 [doi>10.1145/322290.322305]
	11	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]
	12	M. Fredman , M. Saks, The cell probe complexity of dynamic data structures, Proceedings of the twenty-first annual ACM symposium on Theory of computing, p.345-354, May 14-17, 1989, Seattle, Washington, United States [doi>10.1145/73007.73040]
	13	T. Imai, T. Asaao, Dynamic segment intersection with applications, in: Proc. 25th Ann. IEEE Symp. on Foundations of Computer Science (1984) 393-402.
	14	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]
	15	J. A. La Poutré, Lower bounds for the union-find and the split-find problem on pointer machines, Proceedings of the twenty-second annual ACM symposium on Theory of computing, p.34-44, May 13-17, 1990, Baltimore, Maryland, United States [doi>10.1145/100216.100221]
	16	K. Mehlhorn, S. N#her, Dynamic fractional cascading, Algorithmica 5 (1990).
	17	Kurt Mehlhorn , Stefan Näher , Helmut Alt, A lower bound on the complexity of the union-split-find problem, SIAM Journal on Computing, v.17 n.6, p.1093-1102, Dec. 1988 [doi>10.1137/0217070]
	18	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
	19	P.B. Miltersen, On the cell probe complexity of polynomial evaluation, Manuscript 1994.
	20	Peter Bro Miltersen , Sairam Subramanian , Jeffrey Scott Vitter , Roberto Tamassia, Complexity models for incremental computation, Theoretical Computer Science, v.130 n.1, p.203-236, Aug. 1, 1994 [doi>10.1016/0304-3975(94)90159-7]
	21	Pravin M. Vaidya, Space-time trade-offs for orthogonal range queries, SIAM Journal on Computing, v.18 n.4, p.748-758, Aug. 1989 [doi>10.1137/0218051]
	22	P. Van Erode Boas, R. Kaas, E. Zijlstra, Design and implementation of an efficient priority queue, Math. Systems Theory 10 (1977) 99-127.
	23	D.E. Willard, Log-logarithmic worst case range queries are possible in space O(n), Inform. Process. Lett. 17 (1983) 81-84.
	24	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]
	25	A.C. Yao, On the complexity of maintaining partial sums, SIAM J. Comput. 14 (1985) 277- 288.

CITED BY 22

	Gudmund Skovbjerg Frandsen , Johan P. Hansen , Peter Bro Miltersen, Lower bounds for dynamic algebraic problems, Information and Computation, v.171 n.2, p.333-349, December 15, 2001
	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
	Peter Bro Miltersen , Noam Nisan , Shmuel Safra , Avi Wigderson, On data structures and asymmetric communication complexity, Proceedings of the twenty-seventh annual ACM symposium on Theory of computing, p.103-111, May 29-June 01, 1995, Las Vegas, Nevada, United States
	Mikkel Thorup, Faster deterministic sorting and priority queues in linear space, Proceedings of the ninth annual ACM-SIAM symposium on Discrete algorithms, p.550-555, January 25-27, 1998, San Francisco, California, 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
	Paul Beame , Faith E. Fich, Optimal bounds for the predecessor problem, Proceedings of the thirty-first annual ACM symposium on Theory of computing, p.295-304, May 01-04, 1999, Atlanta, Georgia, United States
	Andrej Brodnik , Svante Carlsson , Johan Karlsson , J. Ian Munro, Worst case constant time priority queue, Proceedings of the twelfth annual ACM-SIAM symposium on Discrete algorithms, p.523-528, January 07-09, 2001, Washington, D.C., United States
	Yijie Han, Improved fast interger sorting in linear space, Information and Computation, v.170 n.1, p.81-94, October 10, 2001
	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
	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
	T. S. Jayram , Subhash Khot , Ravi Kumar , Yuval Rabani, Cell-probe lower bounds for the partial match problem, Proceedings of the thirty-fifth annual ACM symposium on Theory of computing, June 09-11, 2003, San Diego, CA, USA
	Paul Beame , Faith E. Fich, Optimal bounds for the predecessor problem and related problems, Journal of Computer and System Sciences, v.65 n.1, p.38-72, August 2002
	Stephen Alstrup , Thore Husfeldt , Theis Rauhe, Dynamic nested brackets, Information and Computation, v.193 n.2, p.75-83, 15 September 2004
	Ding Liu, A strong lower bound for approximate nearest neighbor searching, Information Processing Letters, v.92 n.1, p.23-29, 16 October 2004
	T. S. Jayram , Subhash Khot , Ravi Kumar , Yuval Rabani, Cell-probe lower bounds for the partial match problem, Journal of Computer and System Sciences, v.69 n.3, p.435-447, November 2004
	Andrej Brodnik , Svante Carlsson , Michael L. Fredman , Johan Karlsson , J. Ian Munro, Worst case constant time priority queue, Journal of Systems and Software, v.78 n.3, p.249-256, December 2005
	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
	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
	Mihai Pătraşcu , Mikkel Thorup, Time-space trade-offs for predecessor search, Proceedings of the thirty-eighth annual ACM symposium on Theory of computing, May 21-23, 2006, Seattle, WA, USA
	Mihai Pǎtraşcu , Mikkel Thorup, Randomization does not help searching predecessors, Proceedings of the eighteenth annual ACM-SIAM symposium on Discrete algorithms, p.555-564, January 07-09, 2007, New Orleans, Louisiana
	Pranab Sen , S. Venkatesh, Lower bounds for predecessor searching in the cell probe model, Journal of Computer and System Sciences, v.74 n.3, p.364-385, May, 2008
	Alexander Golynski, Cell probe lower bounds for succinct data structures, Proceedings of the Nineteenth Annual ACM -SIAM Symposium on Discrete Algorithms, p.625-634, January 04-06, 2009, New York, New York