research
∙
07/12/2023
Connectivity Labeling for Multiple Vertex Failures
We present an efficient labeling scheme for answering connectivity queri...
share
research
∙
07/05/2023
Sorting Pattern-Avoiding Permutations via 0-1 Matrices Forbidding Product Patterns
We consider the problem of comparison-sorting an n-permutation S that av...
research
∙
06/28/2023
On the Extremal Functions of Acyclic Forbidden 0-1 Matrices
The extremal theory of forbidden 0-1 matrices studies the asymptotic gro...
research
∙
08/22/2022
Simpler and Better Cardinality Estimators for HyperLogLog and PCSA
Cardinality Estimation (aka Distinct Elements) is a classic problem in s...
research
∙
06/30/2022
Byzantine Agreement with Optimal Resilience via Statistical Fraud Detection
Since the mid-1980s it has been known that Byzantine Agreement can be so...
research
∙
02/27/2022
Byzantine Agreement in Polynomial Time with Near-Optimal Resilience
It has been known since the early 1980s that Byzantine Agreement in the ...
research
∙
01/02/2022
Optimal Vertex Connectivity Oracles
A k-vertex connectivity oracle for undirected G is a data structure that...
research
∙
04/19/2021
Wake Up and Join Me! An Energy-Efficient Algorithm for Maximal Matching in Radio Networks
We consider networks of small, autonomous devices that communicate with ...
research
∙
02/12/2021
The Structure of Minimum Vertex Cuts
In this paper we continue a long line of work on representing the cut st...
research
∙
08/20/2020
Simple and Efficient Cardinality Estimation in Data Streams
We study sketching schemes for the cardinality estimation problem in dat...
research
∙
07/19/2020
The Energy Complexity of BFS in Radio Networks
We consider a model of energy complexity in Radio Networks in which tran...
research
∙
07/16/2020
Planar Distance Oracles with Better Time-Space Tradeoffs
In a recent breakthrough, Charalampopoulos, Gawrychowski, Mozes, and Wei...
research
∙
07/16/2020
Information Theoretic Limits of Cardinality Estimation: Fisher Meets Shannon
In this paper we study the intrinsic tradeoff between the space complexi...
research
∙
04/17/2020
Contention Resolution Without Collision Detection
This paper focuses on the contention resolution problem on a shared comm...
research
∙
12/07/2019
Joins on Samples: A Theoretical Guide for Practitioners
Despite decades of research on approximate query processing (AQP), our u...
research
∙
08/30/2019
The Communication Complexity of Set Intersection and Multiple Equality Testing
In this paper we explore fundamental problems in randomized communicatio...
research
∙
07/17/2018
Distributed Triangle Detection via Expander Decomposition
We present improved distributed algorithms for triangle detection and it...
research
∙
06/22/2018
Improved bounds for multipass pairing heaps and path-balanced binary search trees
We revisit multipass pairing heaps and path-balanced binary search trees...
research
∙
02/17/2018
Lower Bounds on Sparse Spanners, Emulators, and Diameter-reducing shortcuts
We prove better lower bounds on additive spanners and emulators, which a...
research
∙
11/03/2017