research
∙
05/18/2023
(Noisy) Gap Cycle Counting Strikes Back: Random Order Streaming Lower Bounds for Connected Components and Beyond
We continue the study of the communication complexity of gap cycle count...
share
research
∙
12/20/2022
Coloring in Graph Streams via Deterministic and Adversarially Robust Algorithms
In recent years, there has been a growing interest in solving various gr...
research
∙
07/21/2022
Tight Bounds for Monotone Minimal Perfect Hashing
The monotone minimal perfect hash function (MMPHF) problem is the follow...
research
∙
07/19/2022
On Regularity Lemma and Barriers in Streaming and Dynamic Matching
We present a new approach for finding matchings in dense graphs by build...
research
∙
05/14/2021
Fully Dynamic Set Cover via Hypergraph Maximal Matching: An Optimal Approximation Through a Local Approach
In the (fully) dynamic set cover problem, we have a collection of m sets...
research
∙
11/14/2020
Separating the Communication Complexity of Truthful and Non-Truthful Combinatorial Auctions
We provide the first separation in the approximation guarantee achievabl...
research
∙
11/19/2018
A Simple Sublinear-Time Algorithm for Counting Arbitrary Subgraphs via Edge Sampling
In the subgraph counting problem, we are given a input graph G(V, E) and...
research
∙
10/31/2018
