<%@ page language="java" contentType="text/html" %>
<%-- Include common initialisation code --%>
<%@ include file="/arch/common.jsp" %>
<%-- The current tab --%>
<% String currentTab = "Research"; %>
<%-- Content of navigation pane --%>
<%@ include file="nav.jsp" %>
<% showCurrentLink=true; %>
<%-- Current navigation location --%>
<% String currentNav = "Reports and Theses"; %>
<%-- Include the code for the document header --%>
<%@ include file="/arch/header.jsp" %>
Research Report CS-RR-258
<%-- Include the code for the lines and navigation --%>
<%@ include file="/arch/middle.jsp" %>
Per Bro Miltersen,
Lower Bounds for Union-Split-Find Related Problems on Random Access Machines
(December 1, 1993).
Abstract
We prove =(Clog logn ) 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.
Download
cs-rr-258.ps.gz
<%-- Include the code for the document footer --%>
<%@ include file="/arch/footer.jsp" %>