research
∙
06/20/2023
Data Structures for Density Estimation
We study statistical/computational tradeoffs for the following density e...
share
research
∙
03/02/2023
Improved Space Bounds for Learning with Experts
We give improved tradeoffs between space and regret for the online learn...
research
∙
11/06/2022
Exponentially Improving the Complexity of Simulating the Weisfeiler-Lehman Test with Graph Neural Networks
Recent work shows that the expressive power of Graph Neural Networks (GN...
research
∙
12/07/2021
Online Sorting and Translational Packing of Convex Polygons
We investigate various online packing problems in which convex polygons ...
research
∙
04/11/2021
Load Balancing with Dynamic Set of Balls and Bins
In dynamic load balancing, we wish to distribute balls into bins in an e...
research
∙
11/22/2020
Tiling with Squares and Packing Dominos in Polynomial Time
We consider planar tiling and packing problems with polyomino pieces and...
research
∙
04/02/2020
No Repetition: Fast Streaming with Highly Concentrated Hashing
To get estimators that work within a certain error bound with high proba...
research
∙
09/02/2019
Disks in Curves of Bounded Convex Curvature
We say that a simple, closed curve γ in the plane has bounded convex cur...
research
∙
08/14/2019
(Learned) Frequency Estimation Algorithms under Zipfian Distribution
The frequencies of the elements in a data stream are an important statis...
research
∙
05/01/2019
Fast hashing with Strong Concentration Bounds
Previous work on tabulation hashing of Pǎtraşcu and Thorup from STOC'11 ...
research
∙
02/05/2019
Classifying Convex Bodies by their Contact and Intersection Graphs
Suppose that A is a convex body in the plane and that A_1,...,A_n are tr...
research
∙
10/31/2018
Non-Empty Bins with Simple Tabulation Hashing
We consider the hashing of a set X⊆ U with |X|=m using a simple tabulati...
research
∙
04/25/2018
Power of d Choices with Simple Tabulation
Suppose that we are to place m balls into n bins sequentially using the ...
research
∙
08/24/2017