2 citations · 5 across the 16 of their papers we have counts for
6 papers · 1 filter
Local Computation Algorithms for Maximum Matching: New Lower Bounds
Soheil Behnezhad, Mohammad Roghani, Aviad Rubinstein
We study local computation algorithms (LCA) for maximum matching. An LCA does not return its output entirely, but reveals parts of it upon query. For matchings, each query is a ver…
Fast swap regret minimization and applications to approximate correlated equilibria
Binghui Peng, Aviad Rubinstein
We give a simple and computationally efficient algorithm that, for any constant , obtains -swap regret within only rounds; t…
Approximate Earth Mover's Distance in Truly-Subquadratic Time
Lorenzo Beretta, Aviad Rubinstein
We design an additive approximation scheme for estimating the cost of the min-weight bipartite matching problem: given a bipartite graph with non-negative edge costs and $\varepsil…
Quantum Communication Complexity of Classical Auctions
Aviad Rubinstein, Zixin Zhou
We study the fundamental, classical mechanism design problem of single-buyer multi-item Bayesian revenue-maximizing auctions under the lens of communication complexity between the…
Envy-Free Cake-Cutting for Four Agents
Alexandros Hollender, Aviad Rubinstein
In the envy-free cake-cutting problem we are given a resource, usually called a cake and represented as the interval, and a set of agents with heterogeneous preferences…
A constant factor approximation for Nash social welfare with subadditive valuations
Shahar Dobzinski, Wenzheng Li, Aviad Rubinstein +1
We present a constant-factor approximation algorithm for the Nash social welfare maximization problem with subadditive valuations accessible via demand queries. More generally, we…