research
∙
03/31/2022
Prefix Filter: Practically and Theoretically Better Than Bloom
Many applications of approximate membership query data structures, or fi...
share
research
∙
05/05/2020
A Space-Efficient Dynamic Dictionary for Multisets with Constant Time Operations
We consider the dynamic dictionary problem for multisets. Given an upper...
research
∙
05/03/2020
A Dynamic Space-Efficient Filter with Constant Time Operations
A dynamic dictionary is a data structure that maintains sets of cardinal...
research
∙
02/24/2020
Upper Tail Analysis of Bucket Sort and Random Tries
Bucket Sort is known to run in expected linear time when the input keys ...
research
∙
11/12/2019
Fully-Dynamic Space-Efficient Dictionaries and Filters with Constant Number of Memory Accesses
A fully-dynamic dictionary is a data structure for maintaining sets that...
research
∙
02/25/2019
Optimal Distributed Covering Algorithms
We present a time-optimal deterministic distributed algorithm for approx...
research
∙
08/17/2018
Optimal Distributed Weighted Set Cover Approximation
We present a time-optimal deterministic distributed algorithm for approx...
research
∙
05/28/2018
Sacrificing Accuracy for Reduced Computation: Cascaded Inference Based on Softmax Confidence
We study the tradeoff between computational effort and accuracy in a cas...
research
∙
04/04/2018
A Deterministic Distributed 2-Approximation for Weighted Vertex Cover in O( n/ ^2) Rounds
We present a deterministic distributed 2-approximation algorithm for the...
research
∙
02/28/2018