6 papers
Lower Bounds for Linear Hashing via Arithmetic Kakeya
Ainesh Bakshi, Alex Conway, Hanna Komlós +2
Affine modular linear hashing is one of the simplest classical hash families. For a prime , the hash function is obtained by choosing uniformly from and…
An Efficient Private Algorithm for Community Detection
Vincent Cohen-Addad, Alessandro Epasto, Haim Kaplan +2
In this paper, we study the community detection problem in the stochastic block model (SBM) under privacy constraints. We introduce private and highly efficient algorithms for exac…
Bounding the Fragmentation of B-Trees Subject to Batched Insertions
Michael A. Bender, Aaron Bernstein, Nairen Cao +5
The issue of internal fragmentation in data structures is a fundamental challenge in database design. A seminal result of Yao in this field shows that evenly splitting the leaves o…
The Case for External Graph Sketching
Michael A. Bender, MartÃn Farach-Colton, Riko Jacob +3
Algorithms in the data stream model use space to compute some property of an input of size , and many of these algorithms are implemented and used in practice. H…
Nearly Optimal List Labeling
Michael A. Bender, Alex Conway, MartÃn Farach-Colton +4
The list-labeling problem captures the basic task of storing a dynamically changing set of up to elements in sorted order in an array of size . The goal is to…
Layered List Labeling
Michael A. Bender, Alex Conway, Martin Farach-Colton +2
The list-labeling problem is one of the most basic and well-studied algorithmic primitives in data structures, with an extensive literature spanning upper bounds, lower bounds, and…