Aarhus University Seal / Aarhus Universitets segl

Further Unifying the Landscape of Cell Probe Lower Bounds

Publikation: KonferencebidragPaperForskningpeer review

Standard

Further Unifying the Landscape of Cell Probe Lower Bounds. / Larsen, Kasper Green; Starup, Jonathan Lindegaard; Steensgaard, Jesper.

2021. Paper præsenteret ved Happening virtually , -.

Publikation: KonferencebidragPaperForskningpeer review

Harvard

APA

CBE

MLA

Vancouver

Author

Bibtex

@conference{4a0b2ac3dbf04645980dc5a03a9c7d76,
title = "Further Unifying the Landscape of Cell Probe Lower Bounds",
abstract = "In a landmark paper, Patrascu demonstrated how a single lower bound for the static data structure problem of reachability in the butterfly graph, could be used to derive a wealth of new and previous lower bounds via reductions. These lower bounds are tight for numerous static data structure problems. Moreover, he also showed that reachability in the butterfly graph reduces to dynamic marked ancestor, a classic problem used to prove lower bounds for dynamic data structures. Unfortunately, Patrascu's reduction to marked ancestor loses a lg lg n factor and therefore falls short of fully recovering all the previous dynamic data structure lower bounds that follow from marked ancestor. In this paper, we revisit Patrascu's work and give a new lossless reduction to dynamic marked ancestor, thereby establishing reachability in the butterfly graph as a single seed problem from which a range of tight static and dynamic data structure lower bounds follow. ",
keywords = "cs.DS",
author = "Larsen, {Kasper Green} and Starup, {Jonathan Lindegaard} and Jesper Steensgaard",
year = "2021",
month = jan,
day = "11",
language = "English",
note = "Happening virtually : Siam symposium on simplicity in algorithms (SOSA21) ; Conference date: 11-01-2021 Through 12-01-2021",
url = "https://www.siam.org/conferences/cm/conference/sosa21",

}

RIS

TY - CONF

T1 - Further Unifying the Landscape of Cell Probe Lower Bounds

AU - Larsen, Kasper Green

AU - Starup, Jonathan Lindegaard

AU - Steensgaard, Jesper

PY - 2021/1/11

Y1 - 2021/1/11

N2 - In a landmark paper, Patrascu demonstrated how a single lower bound for the static data structure problem of reachability in the butterfly graph, could be used to derive a wealth of new and previous lower bounds via reductions. These lower bounds are tight for numerous static data structure problems. Moreover, he also showed that reachability in the butterfly graph reduces to dynamic marked ancestor, a classic problem used to prove lower bounds for dynamic data structures. Unfortunately, Patrascu's reduction to marked ancestor loses a lg lg n factor and therefore falls short of fully recovering all the previous dynamic data structure lower bounds that follow from marked ancestor. In this paper, we revisit Patrascu's work and give a new lossless reduction to dynamic marked ancestor, thereby establishing reachability in the butterfly graph as a single seed problem from which a range of tight static and dynamic data structure lower bounds follow.

AB - In a landmark paper, Patrascu demonstrated how a single lower bound for the static data structure problem of reachability in the butterfly graph, could be used to derive a wealth of new and previous lower bounds via reductions. These lower bounds are tight for numerous static data structure problems. Moreover, he also showed that reachability in the butterfly graph reduces to dynamic marked ancestor, a classic problem used to prove lower bounds for dynamic data structures. Unfortunately, Patrascu's reduction to marked ancestor loses a lg lg n factor and therefore falls short of fully recovering all the previous dynamic data structure lower bounds that follow from marked ancestor. In this paper, we revisit Patrascu's work and give a new lossless reduction to dynamic marked ancestor, thereby establishing reachability in the butterfly graph as a single seed problem from which a range of tight static and dynamic data structure lower bounds follow.

KW - cs.DS

M3 - Paper

T2 - Happening virtually

Y2 - 11 January 2021 through 12 January 2021

ER -