Techniques for proving data structure lower bounds
Abstract/Contents
- Abstract
- We present several techniques for proving the nonexistence of "too- efficient" data structures. Then we apply these techniques to prove lower bounds for three data structure problems: dynamic interval union, 2D weighted orthogonal range counting, and 2D orthogonal range parity.
Description
| Type of resource | text |
|---|---|
| Form | electronic; electronic resource; remote |
| Extent | 1 online resource. |
| Publication date | 2017 |
| Issuance | monographic |
| Language | English |
Creators/Contributors
| Associated with | Yu, Huacheng |
|---|---|
| Associated with | Stanford University, Computer Science Department. |
| Primary advisor | Reingold, Omer |
| Primary advisor | Williams, Ryan (Richard Ryan) |
| Thesis advisor | Reingold, Omer |
| Thesis advisor | Williams, Ryan (Richard Ryan) |
| Thesis advisor | Valiant, Gregory |
| Advisor | Valiant, Gregory |
Subjects
| Genre | Theses |
|---|
Bibliographic information
| Statement of responsibility | Huacheng Yu. |
|---|---|
| Note | Submitted to the Department of Computer Science. |
| Thesis | Thesis (Ph.D.)--Stanford University, 2017. |
| Location | electronic resource |
Access conditions
- Copyright
- © 2017 by Huacheng Yu
- License
- This work is licensed under a Creative Commons Attribution Non Commercial 3.0 Unported license (CC BY-NC).
Also listed in
Loading usage metrics...