9 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…
Tight Bounds for Memory Allocation With and Without Request Fragmentation
Michael A. Bender, Alex Conway, Martín Farach-Colton +3
The classical memory-allocation problem captures the task of placing objects of different sizes in memory, while minimizing the so-called memory high-water mark. It has been known…
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…
Online List Labeling: Breaking the Barrier
Michael A. Bender, Alex Conway, Martín Farach-Colton +3
The online list labeling problem is an algorithmic primitive with a large literature of upper bounds, lower bounds, and applications. The goal is to store a dynamically-changing se…
Graph Ranking and the Cost of Sybil Defense
Gwendolyn Farach-Colton, Martin Farach-Colton, Leslie Ann Goldberg +5
Ranking functions such as PageRank assign numeric values (ranks) to nodes of graphs, most notably the web graph. Node rankings are an integral part of Internet search algorithms, s…