The Library
Lower bounds for union-split-find related problems on random access machines
Tools
Tools
Tools
Miltersen, Peter Bro (1993) Lower bounds for union-split-find related problems on random access machines. University of Warwick. Department of Computer Science. (Department of Computer Science research report). (Unpublished)
|
PDF (Department of Computer Science Research Report)
WRAP_cs-rr-258.pdf - Other - Requires a PDF viewer. Download (306Kb) | Preview |
Abstract
We prove Ω(√log log n) lower bounds on the random access machine complexity of several dynamic, partially dynamic and static data structure problems, including the union-split-find problem, dynamic prefix problems and one-dimensional range query problems. The proof techniques include a general technique using perfect hashing for reducing static data structure problems (with a restriction of the size of the structure) into partially dynamic data structure problems (with no such restriction), thus providing a way to transfer lower bounds. We use a generalization of a method due to Ajtai for proving the lower bounds on the static problems, but describe the proof in terms of communication complexity, revealing a striking similarity to the proof used by Karchmer and Wigderson for proving lower bounds on the monotone circuit depth of connectivity.
| Item Type: | Report | ||||
|---|---|---|---|---|---|
| Subjects: | Q Science > QA Mathematics > QA76 Electronic computers. Computer science. Computer software | ||||
| Divisions: | Faculty of Science, Engineering and Medicine > Science > Computer Science | ||||
| Library of Congress Subject Headings (LCSH): | Random access memory, Data structures (Computer science) | ||||
| Series Name: | Department of Computer Science research report | ||||
| Publisher: | University of Warwick. Department of Computer Science | ||||
| Official Date: | 1993 | ||||
| Dates: |
|
||||
| Number: | Number 258 | ||||
| Number of Pages: | 13 | ||||
| DOI: | CS-RR-258 | ||||
| Institution: | University of Warwick | ||||
| Theses Department: | Department of Computer Science | ||||
| Status: | Not Peer Reviewed | ||||
| Publication Status: | Unpublished | ||||
| Funder: | Forskningsrådet for Natur og Univers [Danish Science Research Council] (FNU), European Strategic Programme of Research and Development in Information Technology (ESPRIT) | ||||
| Grant number: | 7141 (ESPRIT) | ||||
| Related URLs: |
Request changes or add full text files to a record
Repository staff actions (login required)
 |
View Item |
Downloads
Downloads per month over past year
