
Separating the Communication Complexity of Truthful and NonTruthful Combinatorial Auctions
We provide the first separation in the approximation guarantee achievabl...
read it

Improved Truthful Mechanisms for Subadditive Combinatorial Auctions: Breaking the Logarithmic Barrier
We present a computationallyefficient truthful mechanism for combinator...
read it

MultiPass Graph Streaming Lower Bounds for Cycle Counting, MAXCUT, Matching Size, and Other Problems
Consider the following gap cycle counting problem in the streaming model...
read it

NearQuadratic Lower Bounds for TwoPass Graph Streaming Algorithms
We prove that any twopass graph streaming algorithm for the st reachab...
read it

Improved Bounds for Distributed Load Balancing
In the load balancing problem, the input is an nvertex bipartite graph ...
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, nve...
read it

Palette Sparsification Beyond (Δ+1) Vertex Coloring
A recent palette sparsification theorem of Assadi, Chen, and Khanna [SOD...
read it

When Algorithms for Maximal Independent Set and Maximal Matching Run in SublinearTime
Maximal independent set (MIS), maximal matching (MM), and (Δ+1)coloring...
read it

Improved Truthful Mechanisms for Combinatorial Auctions with Submodular Bidders
A longstanding open problem in Algorithmic Mechanism Design is to design...
read it

Distributed Weighted Matching via Randomized Composable Coresets
Maximum weight matching is one of the most fundamental combinatorial opt...
read it

Polynomial Pass Lower Bounds for Graph Streaming Algorithms
We present new lower bounds that show that a polynomial number of passes...
read it

Distributed and Streaming Linear Programming in Low Dimensions
We study linear programming and general LPtype problems in several big ...
read it

A Simple SublinearTime Algorithm for Counting Arbitrary Subgraphs via Edge Sampling
In the subgraph counting problem, we are given a input graph G(V, E) and...
read it

Secretary Ranking with Minimal Inversions
We study a twist on the classic secretary problem, which we term the sec...
read it

Towards a Unified Theory of Sparsification for Matching Problems
In this paper, we present a construction of a `matching sparsifier', tha...
read it

Stochastic Submodular Cover with Limited Adaptivity
In the submodular cover problem, we are given a nonnegative monotone su...
read it

Sublinear Algorithms for (Δ+ 1) Vertex Coloring
Any graph with maximum degree Δ admits a proper vertex coloring with Δ +...
read it

Fully Dynamic Maximal Independent Set with Sublinear in n Update Time
The first fully dynamic algorithm for maintaining a maximal independent ...
read it

Massively Parallel Algorithms for Finding WellConnected Components in Sparse Graphs
A fundamental question that shrouds the emergence of massively parallel ...
read it

Fully Dynamic Maximal Independent Set with Sublinear Update Time
A maximal independent set (MIS) can be maintained in an evolving medge ...
read it

Tight Bounds on the Round Complexity of the Distributed Maximum Coverage Problem
We study the maximum kset coverage problem in the following distributed...
read it

Coresets Meet EDCS: Algorithms for Matching and Vertex Cover on Massive Graphs
Randomized composable coresets were introduced recently as an effective ...
read it
Sepehr Assadi
is this you? claim profile