2 citations · 5 across the 16 of their papers we have counts for
19 papers
Improved Combinatorial Auctions with and without Samples
Aviad Rubinstein, Sahil Singla
We give new mechanisms for combinatorial auctions in the offline, secretary, and prophet-with-samples models. Specifically, we obtain the following guarantees for social welfare ma…
Tarski Fixed Points in Quasi-FPT Queries
Xi Chen, Ruiquan Gao, Yuhao Li +2
We study the query complexity of finding a Tarski fixed point over . Previous work has left a large gap between and . We show tha…
Approximately Efficient Multidimensional Bilateral Trade
Aviad Rubinstein, Xizhi Tan, Zixin Zhou
A central challenge in mechanism design is to develop truthful trade mechanisms that maximize the expected gains-from-trade (GFT) in two-sided markets. Because achieving the full G…
Welfare Approximation in Multilateral Trade
Tomer Ezra, Aadityan Ganesh, Aviad Rubinstein
We introduce the study of \emph{multilateral trade}: a mechanism-design problem in which a single potential trade involves agents and can be executed only if all agents agr…
Single-Item Auctions with a Monopolist Intermediary
Jingyi Liu, Aviad Rubinstein, Ertem Nusret Tas +2
Classical optimal auction theory assumes that bids reach the seller directly. We study how this picture changes when a revenue-maximizing intermediary controls access to the seller…
Secretary, Prophet, and Stochastic Probing via Big-Decisions-First
Aviad Rubinstein, Sahil Singla
We revisit three fundamental problems in algorithms under uncertainty: the Secretary Problem, Prophet Inequality, and Stochastic Probing, each subject to general downward-closed co…
Approximating Gains-from-Trade in Matching Markets
Moshe Babaioff, Aviad Rubinstein, Xizhi Tan +1
A central challenge in mechanism design is to develop truthful trade mechanisms that maximize the expected gains-from-trade (GFT) in two-sided markets with strategic agents. As ach…
Approximation Schemes for Edit Distance and LCS in Quasi-Strongly Subquadratic Time
Xiao Mao, Aviad Rubinstein
We present novel randomized approximation schemes for the Edit Distance (ED) problem and the Longest Common Subsequence (LCS) problem that, for any constant , compute a $(1+ε)…
Tight Pair Query Lower Bounds for Matching and Earth Mover's Distance
Amir Azarmehr, Soheil Behnezhad, Mohammad Roghani +1
How many adjacency matrix queries (also known as pair queries) are required to estimate the size of a maximum matching in an -vertex graph ? We study this fundamental questio…
Hardness of Approximate Sperner and Applications to Envy-Free Cake Cutting
Ruiquan Gao, Mohammad Roghani, Aviad Rubinstein +1
Given a so called ''Sperner coloring'' of a triangulation of the -dimensional simplex, Sperner's lemma guarantees the existence of a rainbow simplex, i.e. a simplex colored by a…
Parallel Sampling via Counting
Nima Anari, Ruiquan Gao, Aviad Rubinstein
We show how to use parallelization to speed up sampling from an arbitrary distribution on a product space , given oracle access to counting queries: $\mathbb{P}_{X\sim μ…
Approximating Maximum Matching Requires Almost Quadratic Time
Soheil Behnezhad, Mohammad Roghani, Aviad Rubinstein
We study algorithms for estimating the size of maximum matching. This problem has been subject to extensive research. For -vertex graphs, Bhattacharya, Kiss, and Saranurak [FOCS…
The complexity of approximate (coarse) correlated equilibrium for incomplete information games
Binghui Peng, Aviad Rubinstein
We study the iteration complexity of decentralized learning of approximate correlated equilibria in incomplete information games. On the negative side, we prove that in $\mathit{ex…
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…