research
∙
04/11/2023
An Associativity Threshold Phenomenon in Set-Associative Caches
In an α-way set-associative cache, the cache is partitioned into disjoin...
share
research
∙
02/15/2023
Robust and Listening-Efficient Contention Resolution
This paper shows how to achieve contention resolution on a shared commun...
research
∙
10/08/2022
IcebergHT: High Performance PMEM Hash Tables Through Stability and Low Associativity
Modern hash table designs strive to minimize space while maximizing spee...
research
∙
07/24/2022
Contention Resolution for Coded Radio Networks
Randomized backoff protocols, such as exponential backoff, are a powerfu...
research
∙
03/28/2022
GraphZeppelin: Storage-Friendly Sketching for Connected Components on Dynamic Graph Streams
Finding the connected components of a graph is a fundamental problem wit...
research
∙
03/05/2022
Online List Labeling: Breaking the log^2n Barrier
The online list labeling problem is an algorithmic primitive with a larg...
research
∙
11/24/2021
Tiny Pointers
This paper introduces a new data-structural object that we call the tiny...
research
∙
10/31/2021
On the Optimal Time/Space Tradeoff for Hash Tables
For nearly six decades, the central open question in the study of hash t...
research
∙
09/09/2021
All-Purpose Hashing
Despite being one of the oldest data structures in computer science, has...
research
∙
07/05/2021
Incremental Edge Orientation in Forests
For any forest G = (V, E) it is possible to orient the edges E so that n...
research
∙
07/02/2021
Linear Probing Revisited: Tombstones Mark the Death of Primary Clustering
First introduced in 1954, linear probing is one of the oldest data struc...
research
∙
04/27/2020
Batched Predecessor and Sorting with Size-Priced Information in External Memory
In the unit-cost comparison model, a black box takes an input two items ...
research
∙
04/17/2020
Contention Resolution Without Collision Detection
This paper focuses on the contention resolution problem on a shared comm...
research
∙
04/05/2019
Achieving Optimal Backlog in Multi-Processor Cup Games
The single- and multi- processor cup games can be used to model natural ...
research
∙
12/24/2018
The Online Event-Detection Problem
Given a stream S = (s_1, s_2, ..., s_N), a ϕ-heavy hitter is an item s_i...
research
∙
07/04/2018
Optimal Ball Recycling
Balls-and-bins games have been a wildly successful tool for modeling loa...
research
∙
11/05/2017
Bloom Filters, Adaptivity, and the Dictionary Problem
The Bloom filter---or, more generally, an approximate membership query d...
research
∙
08/01/2012