-
Separating the Communication Complexity of Truthful and Non-Truthful Combinatorial Auctions
We provide the first separation in the approximation guarantee achievabl...
11/14/2020 ∙ by Sepehr Assadi, et al. ∙
0
∙
share
read it
-
Improved Truthful Mechanisms for Subadditive Combinatorial Auctions: Breaking the Logarithmic Barrier
We present a computationally-efficient truthful mechanism for combinator...
10/03/2020 ∙ by Sepehr Assadi, et al. ∙
0
∙
share
read it
-
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...
09/07/2020 ∙ by Sepehr Assadi, et al. ∙
0
∙
share
read it
-
Near-Quadratic Lower Bounds for Two-Pass Graph Streaming Algorithms
We prove that any two-pass graph streaming algorithm for the s-t reachab...
09/02/2020 ∙ by Sepehr Assadi, et al. ∙
0
∙
share
read it
-
Improved Bounds for Distributed Load Balancing
In the load balancing problem, the input is an n-vertex bipartite graph ...
08/10/2020 ∙ by Sepehr Assadi, et al. ∙
0
∙
share
read it
-
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...
07/12/2020 ∙ by Sepehr Assadi, et al. ∙
0
∙
share
read it
-
Palette Sparsification Beyond (Δ+1) Vertex Coloring
A recent palette sparsification theorem of Assadi, Chen, and Khanna [SOD...
06/18/2020 ∙ by Noga Alon, et al. ∙
0
∙
share
read it
-
When Algorithms for Maximal Independent Set and Maximal Matching Run in Sublinear-Time
Maximal independent set (MIS), maximal matching (MM), and (Δ+1)-coloring...
06/13/2020 ∙ by Sepehr Assadi, et al. ∙
0
∙
share
read it
-
Improved Truthful Mechanisms for Combinatorial Auctions with Submodular Bidders
A longstanding open problem in Algorithmic Mechanism Design is to design...
11/07/2019 ∙ by Sepehr Assadi, et al. ∙
0
∙
share
read it
-
Distributed Weighted Matching via Randomized Composable Coresets
Maximum weight matching is one of the most fundamental combinatorial opt...
06/05/2019 ∙ by Sepehr Assadi, et al. ∙
0
∙
share
read it
-
Polynomial Pass Lower Bounds for Graph Streaming Algorithms
We present new lower bounds that show that a polynomial number of passes...
04/09/2019 ∙ by Sepehr Assadi, et al. ∙
0
∙
share
read it
-
Distributed and Streaming Linear Programming in Low Dimensions
We study linear programming and general LP-type problems in several big ...
03/13/2019 ∙ by Sepehr Assadi, et al. ∙
0
∙
share
read it
-
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...
11/19/2018 ∙ by Sepehr Assadi, et al. ∙
0
∙
share
read it
-
Secretary Ranking with Minimal Inversions
We study a twist on the classic secretary problem, which we term the sec...
11/15/2018 ∙ by Sepehr Assadi, et al. ∙
0
∙
share
read it
-
Towards a Unified Theory of Sparsification for Matching Problems
In this paper, we present a construction of a `matching sparsifier', tha...
11/05/2018 ∙ by Sepehr Assadi, et al. ∙
0
∙
share
read it
-
Stochastic Submodular Cover with Limited Adaptivity
In the submodular cover problem, we are given a non-negative monotone su...
10/31/2018 ∙ by Arpit Agarwal, et al. ∙
0
∙
share
read it
-
Sublinear Algorithms for (Δ+ 1) Vertex Coloring
Any graph with maximum degree Δ admits a proper vertex coloring with Δ +...
07/24/2018 ∙ by Sepehr Assadi, et al. ∙
0
∙
share
read it
-
Fully Dynamic Maximal Independent Set with Sublinear in n Update Time
The first fully dynamic algorithm for maintaining a maximal independent ...
06/26/2018 ∙ by Sepehr Assadi, et al. ∙
0
∙
share
read it
-
Massively Parallel Algorithms for Finding Well-Connected Components in Sparse Graphs
A fundamental question that shrouds the emergence of massively parallel ...
05/08/2018 ∙ by Sepehr Assadi, et al. ∙
0
∙
share
read it
-
Fully Dynamic Maximal Independent Set with Sublinear Update Time
A maximal independent set (MIS) can be maintained in an evolving m-edge ...
02/27/2018 ∙ by Sepehr Assadi, et al. ∙
0
∙
share
read it
-
Tight Bounds on the Round Complexity of the Distributed Maximum Coverage Problem
We study the maximum k-set coverage problem in the following distributed...
01/09/2018 ∙ by Sepehr Assadi, et al. ∙
0
∙
share
read it
-
Coresets Meet EDCS: Algorithms for Matching and Vertex Cover on Massive Graphs
Randomized composable coresets were introduced recently as an effective ...
11/08/2017 ∙ by Sepehr Assadi, et al. ∙
0
∙
share
read it
