Crossing the Logarithmic Barrier for Dynamic Boolean Data Structure Lower Bounds

Research output: Contribution to book/anthology/report/proceedingArticle in proceedingsResearchpeer-review

Standard

Crossing the Logarithmic Barrier for Dynamic Boolean Data Structure Lower Bounds. / Larsen, Kasper Green; Weinstein, Omri; Yu, Huacheng.

STOC 2018 - Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing. ed. / Monika Henzinger; David Kempe; Ilias Diakonikolas. New York, NY, USA : Association for Computing Machinery, 2018. p. 978-989 (A C M. S I G A C T - S I G M O D - S I G A R T Symposium on Principles of Database Systems. Proceedings; No. 2018).

Research output: Contribution to book/anthology/report/proceedingArticle in proceedingsResearchpeer-review

Harvard

Larsen, KG, Weinstein, O & Yu, H 2018, Crossing the Logarithmic Barrier for Dynamic Boolean Data Structure Lower Bounds. in M Henzinger, D Kempe & I Diakonikolas (eds), STOC 2018 - Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing. Association for Computing Machinery, New York, NY, USA, A C M. S I G A C T - S I G M O D - S I G A R T Symposium on Principles of Database Systems. Proceedings, no. 2018, pp. 978-989, 50th Annual ACM Symposium on Theory of Computing, STOC 2018, Los Angeles, United States, 25/06/2018. https://doi.org/10.1145/3188745.3188790

APA

Larsen, K. G., Weinstein, O., & Yu, H. (2018). Crossing the Logarithmic Barrier for Dynamic Boolean Data Structure Lower Bounds. In M. Henzinger, D. Kempe, & I. Diakonikolas (Eds.), STOC 2018 - Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing (pp. 978-989). New York, NY, USA: Association for Computing Machinery. A C M. S I G A C T - S I G M O D - S I G A R T Symposium on Principles of Database Systems. Proceedings, No. 2018 https://doi.org/10.1145/3188745.3188790

CBE

Larsen KG, Weinstein O, Yu H. 2018. Crossing the Logarithmic Barrier for Dynamic Boolean Data Structure Lower Bounds. Henzinger M, Kempe D, Diakonikolas I, editors. In STOC 2018 - Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing. New York, NY, USA: Association for Computing Machinery. pp. 978-989. (A C M. S I G A C T - S I G M O D - S I G A R T Symposium on Principles of Database Systems. Proceedings; No. 2018). https://doi.org/10.1145/3188745.3188790

MLA

Larsen, Kasper Green, Omri Weinstein and Huacheng Yu "Crossing the Logarithmic Barrier for Dynamic Boolean Data Structure Lower Bounds"., Henzinger, Monika Kempe, David Diakonikolas, Ilias (editors). STOC 2018 - Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing. New York, NY, USA: Association for Computing Machinery. (A C M. S I G A C T - S I G M O D - S I G A R T Symposium on Principles of Database Systems. Proceedings; Journal number 2018). 2018, 978-989. https://doi.org/10.1145/3188745.3188790

Vancouver

Larsen KG, Weinstein O, Yu H. Crossing the Logarithmic Barrier for Dynamic Boolean Data Structure Lower Bounds. In Henzinger M, Kempe D, Diakonikolas I, editors, STOC 2018 - Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing. New York, NY, USA: Association for Computing Machinery. 2018. p. 978-989. (A C M. S I G A C T - S I G M O D - S I G A R T Symposium on Principles of Database Systems. Proceedings; No. 2018). https://doi.org/10.1145/3188745.3188790

Author

Larsen, Kasper Green ; Weinstein, Omri ; Yu, Huacheng. / Crossing the Logarithmic Barrier for Dynamic Boolean Data Structure Lower Bounds. STOC 2018 - Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing. editor / Monika Henzinger ; David Kempe ; Ilias Diakonikolas. New York, NY, USA : Association for Computing Machinery, 2018. pp. 978-989 (A C M. S I G A C T - S I G M O D - S I G A R T Symposium on Principles of Database Systems. Proceedings; No. 2018).

Bibtex

@inproceedings{5451249b07814d35a20e5c67b5013246,
title = "Crossing the Logarithmic Barrier for Dynamic Boolean Data Structure Lower Bounds",
abstract = "This paper proves the first super-logarithmic lower bounds on the cell probe complexity of dynamic boolean (a.k.a. decision) data structure problems, a long-standing milestone in data structure lower bounds. We introduce a new approach and use it to prove a Ω (lg 1.5 n) lower bound on the operational time of a wide range of boolean data structure problems, most notably, on the query time of dynamic range counting over F 2 (Pǎtraşcu, 2007). Proving an (lg n) lower bound for this problem was explicitly posed as one of five important open problems in the late Mihai Pǎtraşcu’s obituary (Thorup, 2013). This result also implies the first (lg n) lower bound for the classical 2D range counting problem, one of the most fundamental data structure problems in computational geometry and spatial databases. We derive similar lower bounds for boolean versions of dynamic polynomial evaluation and 2D rectangle stabbing, and for the (non-boolean) problems of range selection and range median. Our technical centerpiece is a new way of “weakly{"} simulating dynamic data structures using efficient one-way communication protocols with small advantage over random guessing. This simulation involves a surprising excursion to low-degree (Chebyshev) polynomials which May be of independent interest, and offers an entirely new algorithmic angle on the “cell sampling{"} method of Panigrahy et al. (2010).",
keywords = "Cell probe models and lower bounds, Communication Complexity, Computational complexity, Cell probe complexity, Data structures, Dynamic problems, Lower bounds, Range searching, CELL PROBE COMPLEXITY, Dynamic Problems, Data Structures, Range Searching, Cell Probe Complexity, Lower Bounds",
author = "Larsen, {Kasper Green} and Omri Weinstein and Huacheng Yu",
year = "2018",
month = "6",
day = "20",
doi = "10.1145/3188745.3188790",
language = "English",
isbn = "978-1-4503-5559-9",
pages = "978--989",
editor = "Monika Henzinger and David Kempe and Ilias Diakonikolas",
booktitle = "STOC 2018 - Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing",
publisher = "Association for Computing Machinery",

}

RIS

TY - GEN

T1 - Crossing the Logarithmic Barrier for Dynamic Boolean Data Structure Lower Bounds

AU - Larsen, Kasper Green

AU - Weinstein, Omri

AU - Yu, Huacheng

PY - 2018/6/20

Y1 - 2018/6/20

N2 - This paper proves the first super-logarithmic lower bounds on the cell probe complexity of dynamic boolean (a.k.a. decision) data structure problems, a long-standing milestone in data structure lower bounds. We introduce a new approach and use it to prove a Ω (lg 1.5 n) lower bound on the operational time of a wide range of boolean data structure problems, most notably, on the query time of dynamic range counting over F 2 (Pǎtraşcu, 2007). Proving an (lg n) lower bound for this problem was explicitly posed as one of five important open problems in the late Mihai Pǎtraşcu’s obituary (Thorup, 2013). This result also implies the first (lg n) lower bound for the classical 2D range counting problem, one of the most fundamental data structure problems in computational geometry and spatial databases. We derive similar lower bounds for boolean versions of dynamic polynomial evaluation and 2D rectangle stabbing, and for the (non-boolean) problems of range selection and range median. Our technical centerpiece is a new way of “weakly" simulating dynamic data structures using efficient one-way communication protocols with small advantage over random guessing. This simulation involves a surprising excursion to low-degree (Chebyshev) polynomials which May be of independent interest, and offers an entirely new algorithmic angle on the “cell sampling" method of Panigrahy et al. (2010).

AB - This paper proves the first super-logarithmic lower bounds on the cell probe complexity of dynamic boolean (a.k.a. decision) data structure problems, a long-standing milestone in data structure lower bounds. We introduce a new approach and use it to prove a Ω (lg 1.5 n) lower bound on the operational time of a wide range of boolean data structure problems, most notably, on the query time of dynamic range counting over F 2 (Pǎtraşcu, 2007). Proving an (lg n) lower bound for this problem was explicitly posed as one of five important open problems in the late Mihai Pǎtraşcu’s obituary (Thorup, 2013). This result also implies the first (lg n) lower bound for the classical 2D range counting problem, one of the most fundamental data structure problems in computational geometry and spatial databases. We derive similar lower bounds for boolean versions of dynamic polynomial evaluation and 2D rectangle stabbing, and for the (non-boolean) problems of range selection and range median. Our technical centerpiece is a new way of “weakly" simulating dynamic data structures using efficient one-way communication protocols with small advantage over random guessing. This simulation involves a surprising excursion to low-degree (Chebyshev) polynomials which May be of independent interest, and offers an entirely new algorithmic angle on the “cell sampling" method of Panigrahy et al. (2010).

KW - Cell probe models and lower bounds, Communication Complexity, Computational complexity

KW - Cell probe complexity

KW - Data structures

KW - Dynamic problems

KW - Lower bounds

KW - Range searching

KW - CELL PROBE COMPLEXITY

KW - Dynamic Problems

KW - Data Structures

KW - Range Searching

KW - Cell Probe Complexity

KW - Lower Bounds

U2 - 10.1145/3188745.3188790

DO - 10.1145/3188745.3188790

M3 - Article in proceedings

SN - 978-1-4503-5559-9

SP - 978

EP - 989

BT - STOC 2018 - Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing

A2 - Henzinger, Monika

A2 - Kempe, David

A2 - Diakonikolas, Ilias

PB - Association for Computing Machinery

CY - New York, NY, USA

ER -