65 citations · 195 across the 64 of their papers we have counts for
10 papers · 1 filter
Separating the Communication Complexity of Truthful and Non-Truthful Combinatorial Auctions
Sepehr Assadi, Hrishikesh Khandeparkar, Raghuvansh R. Saxena +1
We provide the first separation in the approximation guarantee achievable by truthful and non-truthful combinatorial auctions with polynomial communication. Specifically, we prove…
Semi-Streaming Bipartite Matching in Fewer Passes and Optimal Space
Sepehr Assadi, Arun Jambulapati, Yujia Jin +2
We provide -pass semi-streaming algorithms for computing -approximate maximum cardinality matchings in bipartite graphs. Our most efficient methods ar…
Improved Truthful Mechanisms for Subadditive Combinatorial Auctions: Breaking the Logarithmic Barrier
Sepehr Assadi, Thomas Kesselheim, Sahil Singla
We present a computationally-efficient truthful mechanism for combinatorial auctions with subadditive bidders that achieves an -approximation to the maximum w…
Multi-Pass Graph Streaming Lower Bounds for Cycle Counting, MAX-CUT, Matching Size, and Other Problems
Sepehr Assadi, Gillat Kol, Raghuvansh R. Saxena +1
Consider the following gap cycle counting problem in the streaming model: The edges of a -regular -vertex graph are arriving one-by-one in a stream and we are promised th…
Near-Quadratic Lower Bounds for Two-Pass Graph Streaming Algorithms
Sepehr Assadi, Ran Raz
We prove that any two-pass graph streaming algorithm for the - reachability problem in -vertex directed graphs requires near-quadratic space of bits. As a cor…
Improved Bounds for Distributed Load Balancing
Sepehr Assadi, Aaron Bernstein, Zachary Langley
In the load balancing problem, the input is an -vertex bipartite graph and a positive weight for each client . The algorithm must assign each client…
Palette Sparsification Beyond Vertex Coloring
Noga Alon, Sepehr Assadi
A recent palette sparsification theorem of Assadi, Chen, and Khanna [SODA'19] states that in every -vertex graph with maximum degree , sampling colors per ea…
Graph Connectivity and Single Element Recovery via Linear and OR Queries
Sepehr Assadi, Deeparnab Chakrabarty, Sanjeev Khanna
We study the problem of finding a spanning forest in an undirected, -vertex multi-graph under two basic query models. One is the Linear query model which are linear measurements…
When Algorithms for Maximal Independent Set and Maximal Matching Run in Sublinear-Time
Sepehr Assadi, Shay Solomon
Maximal independent set (MIS), maximal matching (MM), and -coloring in graphs of maximum degree are among the most prominent algorithmic graph theory problems. They are…
Exploration with Limited Memory: Streaming Algorithms for Coin Tossing, Noisy Comparisons, and Multi-Armed Bandits
Sepehr Assadi, Chen Wang
Consider the following abstract coin tossing problem: Given a set of coins with unknown biases, find the most biased coin using a minimal number of coin tosses. This is a commo…