research
∙
07/06/2023
A Simple (1-ε)-Approximation Semi-Streaming Algorithm for Maximum (Weighted) Matching
We present a simple semi-streaming algorithm for (1-ϵ)-approximation of ...
share
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...
research
∙
03/11/2023
Generalizing Greenwald-Khanna Streaming Quantile Summaries for Weighted Inputs
Estimating quantiles, like the median or percentiles, is a fundamental t...
research
∙
01/17/2023
All-Norm Load Balancing in Graph Streams via the Multiplicative Weights Update Method
In the weighted load balancing problem, the input is an n-vertex biparti...
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
∙
11/09/2022
Tight Bounds for Vertex Connectivity in Dynamic Streams
We present a streaming algorithm for the vertex connectivity problem in ...
research
∙
09/29/2022
On Constructing Spanners from Random Gaussian Projections
Graph sketching is a powerful paradigm for analyzing graph structure via...
research
∙
09/19/2022
Rounds vs Communication Tradeoffs for Maximal Independent Sets
We consider the problem of finding a maximal independent set (MIS) in th...
research
∙
09/16/2022
Asymptotically Optimal Bounds for Estimating H-Index in Sublinear Time with Applications to Subgraph Counting
The h-index is a metric used to measure the impact of a user in a public...
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
∙
07/03/2022
Decremental Matching in General Graphs
We consider the problem of maintaining an approximate maximum integral m...
research
∙
05/28/2022
Fine-Grained Buy-Many Mechanisms Are Not Much Better Than Bundling
Multi-item optimal mechanisms are known to be extremely complex, often o...
research
∙
03/21/2022
Brooks' Theorem in Graph Streams: A Single-Pass Semi-Streaming Algorithm for Δ-Coloring
Every graph with maximum degree Δ can be colored with (Δ+1) colors using...
research
∙
01/30/2022
An Asymptotically Optimal Algorithm for Maximum Matching in Dynamic Streams
We present an algorithm for the maximum matching problem in dynamic (ins...
research
∙
09/30/2021
Deterministic Graph Coloring in the Streaming Model
Recent breakthroughs in graph streaming have led to the design of single...
research
∙
08/16/2021
A Two-Pass Lower Bound for Semi-Streaming Maximum Matching
We prove a lower bound on the space complexity of two-pass semi-streamin...
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
∙
04/11/2021
Graph Streaming Lower Bounds for Parameter Estimation and Property Testing via a Streaming XOR Lemma
We study space-pass tradeoffs in graph streaming algorithms for paramete...
research
∙
02/13/2021
Beating Two-Thirds For Random-Order Streaming Matching
We study the maximum matching problem in the random-order semi-streaming...
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
∙
10/03/2020
Improved Truthful Mechanisms for Subadditive Combinatorial Auctions: Breaking the Logarithmic Barrier
We present a computationally-efficient truthful mechanism for combinator...
research
∙
09/07/2020
Multi-Pass Graph Streaming Lower Bounds for Cycle Counting, MAX-CUT, Matching Size, and Other Problems
Consider the following gap cycle counting problem in the streaming model...
research
∙
09/02/2020
Near-Quadratic Lower Bounds for Two-Pass Graph Streaming Algorithms
We prove that any two-pass graph streaming algorithm for the s-t reachab...
research
∙
08/10/2020
Improved Bounds for Distributed Load Balancing
In the load balancing problem, the input is an n-vertex bipartite graph ...
research
∙
07/12/2020
Graph Connectivity and Single Element Recovery via Linear and OR Queries
We study the problem of finding a spanning forest in an undirected, n-ve...
research
∙
06/18/2020
Palette Sparsification Beyond (Δ+1) Vertex Coloring
A recent palette sparsification theorem of Assadi, Chen, and Khanna [SOD...
research
∙
06/13/2020
When Algorithms for Maximal Independent Set and Maximal Matching Run in Sublinear-Time
Maximal independent set (MIS), maximal matching (MM), and (Δ+1)-coloring...
research
∙
11/07/2019
Improved Truthful Mechanisms for Combinatorial Auctions with Submodular Bidders
A longstanding open problem in Algorithmic Mechanism Design is to design...
research
∙
06/05/2019
Distributed Weighted Matching via Randomized Composable Coresets
Maximum weight matching is one of the most fundamental combinatorial opt...
research
∙
04/09/2019
Polynomial Pass Lower Bounds for Graph Streaming Algorithms
We present new lower bounds that show that a polynomial number of passes...
research
∙
03/13/2019
Distributed and Streaming Linear Programming in Low Dimensions
We study linear programming and general LP-type problems in several big ...
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
∙
11/15/2018
Secretary Ranking with Minimal Inversions
We study a twist on the classic secretary problem, which we term the sec...
research
∙
11/05/2018
Towards a Unified Theory of Sparsification for Matching Problems
In this paper, we present a construction of a `matching sparsifier', tha...
research
∙
10/31/2018
Stochastic Submodular Cover with Limited Adaptivity
In the submodular cover problem, we are given a non-negative monotone su...
research
∙
07/24/2018
Sublinear Algorithms for (Δ+ 1) Vertex Coloring
Any graph with maximum degree Δ admits a proper vertex coloring with Δ +...
research
∙
06/26/2018
Fully Dynamic Maximal Independent Set with Sublinear in n Update Time
The first fully dynamic algorithm for maintaining a maximal independent ...
research
∙
05/08/2018
Massively Parallel Algorithms for Finding Well-Connected Components in Sparse Graphs
A fundamental question that shrouds the emergence of massively parallel ...
research
∙
02/27/2018
Fully Dynamic Maximal Independent Set with Sublinear Update Time
A maximal independent set (MIS) can be maintained in an evolving m-edge ...
research
∙
01/09/2018
Tight Bounds on the Round Complexity of the Distributed Maximum Coverage Problem
We study the maximum k-set coverage problem in the following distributed...
research
∙
11/08/2017