Aviad Rubinstein

ICML Conference 2025 Conference Paper

A Near Linear Query Lower Bound for Submodular Maximization

• Binghui Peng
• Aviad Rubinstein

We revisit the problem of selecting $k$-out-of-$n$ elements with the goal of optimizing an objective function, and ask whether it can be solved approximately with sublinear query complexity. For objective functions that are monotone submodular, [Li, Feldman, Kazemi, Karbasi, NeurIPS’22; Kuhnle, AISTATS’21] gave an $\Omega(n/k)$ query lower bound for approximating to within any constant factor. We strengthen their lower bound to a nearly tight $\tilde{\Omega}(n)$. This lower bound holds even for estimating the value of the optimal subset. When the objective function is additive, we prove that finding an approximately optimal subset still requires near-linear query complexity, but we can estimate the value of the optimal subset in $\tilde{O}(n/k)$ queries, and that this is tight up to polylog factors.

FOCS Conference 2025 Conference Paper

High-to-Low Dimensional PPA-completeness: Borsuk-Ulam, Tucker, Consensus Halving, and Ham Sandwich

• Ruiquan Gao 0001
• Alexandros Hollender
• Aviad Rubinstein

The Borsuk-Ulam theorem states that every continuous odd function $f: {\mathcal{S}}^{n} \rightarrow \mathbb{R}^{n}$ must have a zero, i. e. , an $x \in {\mathcal{S}}^{n}$ such that $f(x)=0$. While such a zero is guaranteed to exist, finding it is known to be computationally intractable: it is PPAcomplete already for n = 2. In this work, we show that the problem remains just as hard even if the function is mapping from a higher to a lower dimensional space. Namely, we prove that it is PPA-complete to find a zero of $f: {\mathcal{S}}^{k} \rightarrow \mathbb{R}^{n}$ for any constants $k \geq n \geq 2$. This result has very appealing consequences for other flagship PPA-complete problems such as Tucker, Consensus Halving, and Ham Sandwich. For example, in the Consensus Halving problem from fair division, we show that finding a partition that satisfies three agents with monotone valuations is PPA-complete, even if we allow any arbitrarily large constant number of cuts.

FOCS Conference 2025 Conference Paper

Tight Pair Query Lower Bounds for Matching and Earth Mover's Distance

• Amir Azarmehr
• Soheil Behnezhad
• Mohammad Roghani
• Aviad Rubinstein

How many adjacency matrix queries (also known as pair queries) are required to estimate the size of a maximum matching in an n-vertex graph G? We study this fundamental question in this paper. On the upper bound side, an algorithm of Bhattacharya, Kiss, and Saranurak [FOCS’23] gives an estimate that is within $\varepsilon n$ of the right bound with $n^{2-\Omega_{\varepsilon}(1)}$ queries, which is subquadratic in n (and thus sublinear in the matrix size) for any fixed $\varepsilon\gt0$. On the lower bound side, while there has been a lot of progress in the adjacency list model, no non-trivial lower bound has been established for algorithms with adjacency matrix query access. In particular, the only known lower bound is a folklore bound of $\Omega(n)$, leaving a huge gap. In this paper, we present the first superlinear in n lower bound for this problem. In fact, we close the gap mentioned above entirely by showing that the algorithm of [BKS’23] is optimal. Formally, we prove that for any fixed $\delta\gt0$, there is a fixed $\varepsilon\gt0$ such that an estimate that is within $\varepsilon n$ of the true bound requires $\Omega\left(n^{2-\delta}\right)$ adjacency matrix queries. Our lower bound also has strong implications for estimating the earth mover’s distance between distributions. For this problem, Beretta and Rubinstein [STOC’24] gave an $n^{2-\Omega_{\varepsilon}(1)}$ time algorithm that obtains an additive $\varepsilon$-approximation and works for any distance function. Whether this can be improved generally, or even for metric spaces, had remained open. Our lower bound rules out the possibility of any improvements over this bound, even under the strong assumption that the underlying distances are in a (1, 2)-metric.

STOC Conference 2024 Conference Paper

A Constant-Factor Approximation for Nash Social Welfare with Subadditive Valuations

• Shahar Dobzinski
• Wenzheng Li
• Aviad Rubinstein
• Jan Vondrák

We present a constant-factor approximation algorithm for the Nash Social Welfare (NSW) maximization problem with subadditive valuations accessible via demand queries. More generally, we propose a framework for NSW optimization which assumes two subroutines which (1) solve a configuration-type LP under certain additional conditions, and (2) round the fractional solution with respect to utilitarian social welfare. In particular, a constant-factor approximation for submodular valuations with value queries can also be derived from our framework.

STOC Conference 2024 Conference Paper

Approximate Earth Mover's Distance in Truly-Subquadratic Time

• Lorenzo Beretta 0001
• Aviad Rubinstein

STOC Conference 2024 Conference Paper

Approximating Maximum Matching Requires Almost Quadratic Time

• Soheil Behnezhad
• Mohammad Roghani
• Aviad Rubinstein

STOC Conference 2024 Conference Paper

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 ε>0, obtains ε T -swap regret within only T = ( n ) rounds; this is an exponential improvement compared to the super-linear number of rounds required by the state-of-the-art algorithm, and resolves the main open problem of ‍[]. Our algorithm has an exponential dependence on ε, but we prove a new, matching lower bound. Our algorithm for swap regret implies faster convergence to ε-Correlated Equilibrium (ε-CE) in several regimes: For normal form two-player games with n actions, it implies the first uncoupled dynamics that converges to the set of ε-CE in polylogarithmic rounds; a ( n )-bit communication protocol for ε-CE in two-player games (resolving an open problem mentioned by ‍[, ]); and an Õ( n )-query algorithm for ε-CE (resolving an open problem of ‍[] and obtaining the first separation between ε-CE and ε-Nash equilibrium in the query complexity model). For extensive-form games, our algorithm implies a PTAS for normal form correlated equilibria , a solution concept often conjectured to be computationally intractable (e.g. ‍[, ]).

FOCS Conference 2024 Conference Paper

Hardness of Approximate Sperner and Applications to Envy-Free Cake Cutting

• Ruiquan Gao 0001
• Mohammad Roghani
• Aviad Rubinstein
• Amin Saberi

Given a so called “Sperner coloring” of a triangulation of the $D$ -dimensional simplex, Sperner's lemma guarantees the existence of a rainbow simplex, i. e. a simplex colored by all $D+1$ colors. However, finding a rainbow simplex was the first problem to be proven PPAD-complete in Papadimitriou's classical paper introducing the class PPAD [1]. In this paper, we prove that the problem does not become easier if we relax “all - ${D}+1$ colors” to allow some fraction of missing colors: in fact, for any constant $D$, finding even a simplex with just three colors remains PPAD-complete! Our result has an interesting application for the envy-free cake cutting from fair division. It is known that if agents value pieces of cake using general continuous functions satisfying a simple boundary condition (“a non-empty piece is better than an empty piece of cake”), there exists an envy-free allocation with connected pieces. We show that for any constant number of agents it is PPAD-complete to find an allocation -even using any constant number of possibly disconnected pieces- that makes just three agents envy-free. Our results extend to super-constant dimension, number of agents, and number of pieces, as long as they are asymptotically bounded by any $\log^{1-\Omega(1)}(\varepsilon)$, where $\varepsilon$ is the precision parameter (side length for Sperner and approximate envy-free for cake cutting).

STOC Conference 2024 Conference Paper

Parallel Sampling via Counting

• Nima Anari
• Ruiquan Gao 0001
• Aviad Rubinstein

We show how to use parallelization to speed up sampling from an arbitrary distribution µ on a product space [ q ] n , given oracle access to counting queries: ℙ X ∼ µ [ X S =σ S ] for any S ⊆ [ n ] and σ S ∈ [ q ] S . Our algorithm takes O ( n 2/3 · polylog( n , q )) parallel time, to the best of our knowledge, the first sublinear in n runtime for arbitrary distributions. Our results have implications for sampling in autoregressive models. Our algorithm directly works with an equivalent oracle that answers conditional marginal queries ℙ X ∼ µ [ X i =σ i | X S =σ S ], whose role is played by a trained neural network in autoregressive models. This suggests a roughly n 1/3 -factor speedup is possible for sampling in any-order autoregressive models. We complement our positive result by showing a lower bound of Ω( n 1/3 ) for the runtime of any parallel sampling algorithm making at most poly( n ) queries to the counting oracle, even for q =2.

SODA Conference 2023 Conference Paper

Beating Greedy Matching in Sublinear Time

• Soheil Behnezhad
• Mohammad Roghani
• Aviad Rubinstein
• Amin Saberi

We study sublinear time algorithms for estimating the size of maximum matching in graphs. Our main result is a (½ + Ω(1))-approximation algorithm which can be implemented in O ( n 1+ε ) time, where n is the number of vertices and the constant ε > 0 can be made arbitrarily small. The best known lower bound for the problem is Ω( n ), which holds for any constant approximation. Existing algorithms either obtain the greedy bound of ½-approximation [Behnezhad FOCS'21], or require some assumption on the maximum degree to run in o ( n 2 )-time [Yoshida, Yamamoto, and Ito STOC'09]. We improve over these by designing a less “adaptive” augmentation algorithm for maximum matching that might be of independent interest.

FOCS Conference 2023 Conference Paper

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 $[0, 1]$ interval, and a set of n agents with heterogeneous preferences over pieces of the cake. The goal is to divide the cake among the n agents such that no agent is envious of any other agent. Even under a very general preferences model, this fundamental fair division problem is known to always admit an exact solution where each agent obtains a connected piece of the cake; we study the complexity of finding an approximate solution, i. e. , a connected $\varepsilon$-envy-free allocation. For monotone valuations of cake pieces, Deng, Qi, and Saberi (2012) gave an efficient (poly $(\log (1 / \varepsilon))$ queries) algorithm for three agents and posed the open problem of four (or more) monotone agents. Even for the special case of additive valuations, Bránzei and Nisan (2022) conjectured an $\Omega(1 / \varepsilon)$ lower bound on the number of queries for four agents. We provide the first efficient algorithm for finding a connected $\varepsilon$-envy-free allocation with four monotone agents. We also prove that as soon as valuations are allowed to be non-monotone, the problem becomes hard: it becomes PPAD-hard, requires poly $(1 / \varepsilon)$ queries in the black-box model, and even poly $(1 / \varepsilon)$ communication complexity. This constitutes, to the best of our knowledge, the first intractability result for any version of the cake-cutting problem in the communication complexity model.

FOCS Conference 2023 Conference Paper

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 vertex v; the LCA should return whether v is matched—and if so to which neighbor—while spending a small time per query. In this paper, we prove that any LCA that computes a matching that is at most an additive of $\epsilon n$ smaller than the maximum matching in n-vertex graphs of maximum degree $\Delta$ must take at least $\Delta^{\Omega(1 / \varepsilon)}$ time. This comes close to the existing upper bounds that take $(\Delta / \epsilon)^{O\left(1 / \epsilon^{2}\right)} \operatorname{polylog}(n)$ time. In terms of sublinear time algorithms, our techniques imply that any algorithm that estimates the size of maximum matching up to an additive error of $\epsilon n$ must take $\Delta^{\Omega(1 / \epsilon)}$ time. This negatively resolves a decade old open problem of the area (see Open Problem 39 of sublinear. info) on whether such estimates can be achieved in $\operatorname{poly}(\Delta / \epsilon)$ time.

FOCS Conference 2023 Conference Paper

Near Optimal Memory-Regret Tradeoff for Online Learning

• Binghui Peng
• Aviad Rubinstein

In the experts problem, on each of T days, an agent needs to follow the advice of one of n “experts”. After each day, the loss associated with each expert’s advice is revealed. A fundamental result in learning theory says that the agent can achieve vanishing regret, i. e. their cumulative loss is within $o(T)$ of the cumulative loss of the best-in-hindsight expert. Can the agent perform well without sufficient space to remember all the experts? We extend a nascent line of research on this question in two directions: 1) We give a new algorithm against the oblivious adversary, improving over the memory-regret tradeoff obtained by [PZ23], and nearly matching the lower bound of [SWXZ22]. 2) We also consider an adaptive adversary who can observe past experts chosen by the agent. In this setting we give both a new algorithm and a novel lower bound, proving that roughly $\sqrt{n}$ memory is both necessary and sufficient for obtaining $o(T)$ regret.

STOC Conference 2023 Conference Paper

Sublinear Time Algorithms and Complexity of Approximate Maximum Matching

• Soheil Behnezhad
• Mohammad Roghani
• Aviad Rubinstein

Sublinear time algorithms for approximating maximum matching size have long been studied. Much of the progress over the last two decades on this problem has been on the algorithmic side. For instance, an algorithm of [Behnezhad; FOCS’21] obtains a 1/2-approximation in O ( n ) time for n -vertex graphs. A more recent algorithm by [Behnezhad, Roghani, Rubinstein, and Saberi; SODA’23] obtains a slightly-better-than-1/2 approximation in O ( n 1+є ) time (for arbitrarily small constant ε>0). On the lower bound side, [Parnas and Ron; TCS’07] showed 15 years ago that obtaining any constant approximation of maximum matching size requires Ω( n ) time. Proving any super-linear in n lower bound, even for (1−є)-approximations, has remained elusive since then. In this paper, we prove the first super-linear in n lower bound for this problem. We show that at least n 1.2 − o (1) queries in the adjacency list model are needed for obtaining a (2/3 + Ω(1))-approximation of the maximum matching size. This holds even if the graph is bipartite and is promised to have a matching of size Θ( n ). Our lower bound argument builds on techniques such as correlation decay that to our knowledge have not been used before in proving sublinear time lower bounds. We complement our lower bound by presenting two algorithms that run in strongly sublinear time of n 2−Ω(1) . The first algorithm achieves a (2/3−ε)-approximation (for any arbitrarily small constant ε>0); this significantly improves prior close-to-1/2 approximations. Our second algorithm obtains an even better approximation factor of (2/3+Ω(1)) for bipartite graphs. This breaks 2/3-approximation which has been a barrier in various settings of the matching problem, and importantly shows that our n 1.2− o (1) time lower bound for (2/3+Ω(1))-approximations cannot be improved all the way to n 2− o (1) .

NeurIPS Conference 2021 Conference Paper

Cardinality constrained submodular maximization for random streams

• Paul Liu
• Aviad Rubinstein
• Jan Vondrak
• Junyao Zhao

We consider the problem of maximizing submodular functions in single-pass streaming and secretaries-with-shortlists models, both with random arrival order. For cardinality constrained monotone functions, Agrawal, Shadravan, and Stein~\cite{SMC19} gave a single-pass $(1-1/e-\varepsilon)$-approximation algorithm using only linear memory, but their exponential dependence on $\varepsilon$ makes it impractical even for $\varepsilon=0. 1$. We simplify both the algorithm and the analysis, obtaining an exponential improvement in the $\varepsilon$-dependence (in particular, $O(k/\varepsilon)$ memory). Extending these techniques, we also give a simple $(1/e-\varepsilon)$-approximation for non-monotone functions in $O(k/\varepsilon)$ memory. For the monotone case, we also give a corresponding unconditional hardness barrier of $1-1/e+\varepsilon$ for single-pass algorithms in randomly ordered streams, even assuming unlimited computation. Finally, we show that the algorithms are simple to implement and work well on real world datasets.

STOC Conference 2021 Conference Paper

Exponential communication separations between notions of selfishness

• Aviad Rubinstein
• Raghuvansh R. Saxena
• Clayton Thomas
• S. Matthew Weinberg
• Junyao Zhao 0001

We consider the problem of implementing a fixed social choice function between multiple players (which takes as input a type t i from each player i and outputs an outcome f ( t 1 ,…, t n )), in which each player must be incentivized to follow the protocol. In particular, we study the communication requirements of a protocol which: (a) implements f , (b) implements f and computes payments that make it ex-post incentive compatible (EPIC) to follow the protocol, and (c) implements f and computes payments in a way that makes it dominant-strategy incentive compatible (DSIC) to follow the protocol. We show exponential separations between all three of these quantities, already for just two players. That is, we first construct an f such that f can be implemented in communication c , but any EPIC implementation of f (with any choice of payments) requires communication exp( c ). This answers an open question of [Fadel and Segal, 2009; Babaioff et. al., 2013]. Second, we construct an f such that an EPIC protocol implements f with communication C , but all DSIC implementations of f require communication exp( C ).

STOC Conference 2021 Conference Paper

Settling the complexity of Nash equilibrium in congestion games

• Yakov Babichenko
• Aviad Rubinstein

We consider (i) the problem of finding a (possibly mixed) Nash equilibrium in congestion games, and (ii) the problem of finding an (exponential precision) fixed point of the gradient descent dynamics of a smooth function f :[0,1] n → ℝ. We prove that these problems are equivalent. Our result holds for various explicit descriptions of f , ranging from (almost general) arithmetic circuits, to degree-5 polynomials. By a very recent result of [Fearnley et al., STOC 2021], this implies that these problems are PPAD ∩ PLS -complete. As a corollary, we also obtain the following equivalence of complexity classes:

STOC Conference 2021 Conference Paper

The randomized communication complexity of randomized auctions

• Aviad Rubinstein
• Junyao Zhao 0001

FOCS Conference 2020 Conference Paper

Communication complexity of Nash equilibrium in potential games (extended abstract)

• Yakov Babichenko
• Aviad Rubinstein

We prove communication complexity lower bounds for (possibly mixed) Nash equilibrium in potential games. In particular, we show that finding a Nash equilibrium requires poly(N) communication in two-player N×N potential games, and 2 poly(n) communication in n-player two-action games. To the best of our knowledge, these are the first results to demonstrate hardness in any model of (possibly mixed) Nash equilibrium in potential games.

STOC Conference 2020 Conference Paper

Constant-factor approximation of near-linear edit distance in near-linear time

• Joshua Brakensiek
• Aviad Rubinstein

We show that the edit distance between two strings of length n can be computed via a randomized algorithm within a factor of f (є) in n 1+є time as long as the edit distance is at least n 1−δ for some δ(є) > 0.

STOC Conference 2020 Conference Paper

Does preprocessing help in fast sequence comparisons?

• Elazar Goldenberg
• Aviad Rubinstein
• Barna Saha

We study edit distance computation with preprocessing: the preprocessing algorithm acts on each string separately, and then the query algorithm takes as input the two preprocessed strings. This model is inspired by scenarios where we would like to compute edit distance between many pairs in the same pool of strings.

NeurIPS Conference 2020 Conference Paper

Hitting the High Notes: Subset Selection for Maximizing Expected Order Statistics

• Aranyak Mehta
• Uri Nadav
• Alexandros Psomas
• Aviad Rubinstein

We consider the fundamental problem of selecting $k$ out of $n$ random variables in a way that the expected highest or second-highest value is maximized. This question captures several applications where we have uncertainty about the quality of candidates (e. g. auction bids, search results) and have the capacity to explore only a small subset due to an exogenous constraint. For example, consider a second price auction where system constraints (e. g. , costly retrieval or model computation) allow the participation of only $k$ out of $n$ bidders, and the goal is to optimize the expected efficiency (highest bid) or expected revenue (second highest bid). We study the case where we are given an explicit description of each random variable. We give a PTAS for the problem of maximizing the expected highest value. For the second-highest value, we prove a hardness result: assuming the Planted Clique Hypothesis, there is no constant factor approximation algorithm that runs in polynomial time. Surprisingly, under the assumption that each random variable has monotone hazard rate (MHR), a simple score-based algorithm, namely picking the $k$ random variables with the largest $1/\sqrt{k}$ top quantile value, is a constant approximation to the expected highest and second highest value, \emph{simultaneously}.

SODA Conference 2020 Conference Paper

Reducing approximate Longest Common Subsequence to approximate Edit Distance

• Aviad Rubinstein
• Zhao Song 0002

FOCS Conference 2020 Conference Paper

Smoothed Complexity of 2-player Nash Equilibria

• Shant Boodaghians
• Joshua Brakensiek
• Samuel B. Hopkins 0001
• Aviad Rubinstein

We prove that computing a Nash equilibrium of a two-player ( n×n) game with payoffs in [-1, 1] is PPAD-hard (under randomized reductions) even in the smoothed analysis setting, smoothing with noise of constant magnitude. This gives a strong negative answer to conjectures of Spielman and Teng [ST06] and Cheng, Deng, and Teng [CDT09]. In contrast to prior work proving PPAD-hardness after smoothing by noise of magnitude 1/poly(n) [CDT09], our smoothed complexity result is not proved via hardness of approximation for Nash equilibria. This is by necessity, since Nash equilibria can be approximated to constant error in quasi-polynomial time [LMM03]. Our results therefore separate smoothed complexity and hardness of approximation for Nash equilibria in two-player games. The key ingredient in our reduction is the use of a random zero-sum game as a gadget to produce two-player games which remain hard even after smoothing. Our analysis crucially shows that all Nash equilibria of random zero-sum games are far from pure (with high probability), and that this remains true even after smoothing.

SODA Conference 2019 Conference Paper

An Exponential Speedup in Parallel Running Time for Submodular Maximization without Loss in Approximation

• Eric Balkanski
• Aviad Rubinstein
• Yaron Singer

STOC Conference 2019 Conference Paper

An optimal approximation for submodular maximization under a matroid constraint in the adaptive complexity model

• Eric Balkanski
• Aviad Rubinstein
• Yaron Singer

In this paper we study submodular maximization under a matroid constraint in the adaptive complexity model. This model was recently introduced in the context of submodular optimization to quantify the information theoretic complexity of black-box optimization in a parallel computation model. Informally, the adaptivity of an algorithm is the number of sequential rounds it makes when each round can execute polynomially-many function evaluations in parallel. Since submodular optimization is regularly applied on large datasets we seek algorithms with low adaptivity to enable speedups via parallelization. Consequently, a recent line of work has been devoted to designing constant factor approximation algorithms for maximizing submodular functions under various constraints in the adaptive complexity model.

FOCS Conference 2019 Conference Paper

Approximation Algorithms for LCS and LIS with Truly Improved Running Times

• Aviad Rubinstein
• Saeed Seddighin
• Zhao Song 0002
• Xiaorui Sun

Longest common subsequence (LCS) is a classic and central problem in combinatorial optimization. While LCS admits a quadratic time solution, recent evidence suggests that solving the problem may be impossible in truly subquadratic time. A special case of LCS wherein each character appears at most once in every string is equivalent to the longest increasing subsequence problem (LIS) which can be solved in quasilinear time. In this work, we present novel algorithms for approximating LCS in truly subquadratic time and LIS in truly sublinear time. Our approximation factors depend on the ratio of the optimal solution size over the input size. We denote this ratio by λ and obtain the following results for LCS and LIS without any prior knowledge of λ. • A truly subquadratic time algorithm for LCS with approximation factor O(λ^3). • A truly sublinear time algorithm for LIS with approximation factor O(λ^3). Triangle inequality was recently used by Boroujeni et al. [1] and Chakraborty et al. [2] to present new approximation algorithms for edit distance. Our techniques for LCS extend the notion of triangle inequality to non-metric settings.

SODA Conference 2019 Conference Paper

Fine-grained Complexity Meets IP = PSPACE

• Lijie Chen 0001
• Shafi Goldwasser
• Kaifeng Lyu
• Guy N. Rothblum
• Aviad Rubinstein

In this paper we study the fine-grained complexity of finding exact and approximate solutions to problems in P. Our main contribution is showing reductions from an exact to an approximate solution for a host of such problems. As one (notable) example, we show that the Closest-LCS-Pair problem (Given two sets of strings A and B, compute exactly the maximum LCS( a, b ) with ( a, b ) ∊ A × B ) is equivalent to its approximation version (under near-linear time reductions, and with a constant approximation factor). More generally, we identify a class of problems, which we call BP-Pair-Class, comprising both exact and approximate solutions, and show that they are all equivalent under near-linear time reductions. Exploring this class and its properties, we also show: Under the NC-SETH assumption (a significantly more relaxed assumption than SETH), solving any of the problems in this class requires essentially quadratic time. Modest improvements on the running time of known algorithms (shaving log factors) would imply that NEXP is not in non-uniform NC 1. Finally, we leverage our techniques to show new barriers for deterministic approximation algorithms for LCS. A very important consequence of our results is that they continue to hold in the data structure setting. In particular, it shows that a data structure for approximate Nearest Neighbor Search for LCS (NNS LCS ) implies a data structure for exact NNS LCS and a data structure for answering regular expression queries with essentially the same complexity. At the heart of these new results is a deep connection between interactive proof systems for bounded-space computations and the fine-grained complexity of exact and approximate solutions to problems in P. In particular, our results build on the proof techniques from the classical IP = PSPACE result.

STOC Conference 2019 Conference Paper

Near-linear time insertion-deletion codes and (1+ ε )-approximating edit distance via indexing

• Bernhard Haeupler
• Aviad Rubinstein
• Amirbehshad Shahrasbi

We introduce fast-decodable indexing schemes for edit distance which can be used to speed up edit distance computations to near-linear time if one of the strings is indexed by an indexing string I . In particular, for every length n and every ε >0, one can in near linear time construct a string I ∈ Σ′ n with |Σ′| = O ε (1), such that, indexing any string S ∈ Σ n , symbol-by-symbol, with I results in a string S ′ ∈ Σ″ n where Σ″ = Σ × Σ′ for which edit distance computations are easy, i.e., one can compute a (1+ε)-approximation of the edit distance between S ′ and any other string in O ( n (log n )) time.

STOC Conference 2018 Conference Paper

Hardness of approximate nearest neighbor search

• Aviad Rubinstein

We prove conditional near-quadratic running time lower bounds for approximate Bichromatic Closest Pair with Euclidean, Manhattan, Hamming, or edit distance. Specifically, unless the Strong Exponential Time Hypothesis (SETH) is false, for every δ>0 there exists a constant ε>0 such that computing a (1+ε)-approximation to the Bichromatic Closest Pair requires Ω( n 2−δ ) time. In particular, this implies a near-linear query time for Approximate Nearest Neighbor search with polynomial preprocessing time. Our reduction uses the recently introduced Distributed PCP framework, but obtains improved efficiency using Algebraic Geometry (AG) codes. Efficient PCPs from AG codes have been constructed in other settings before, but our construction is the first to yield new hardness results.

FOCS Conference 2018 Conference Paper

Near-Optimal Communication Lower Bounds for Approximate Nash Equilibria

• Mika Göös
• Aviad Rubinstein

We prove an N 2-o(1) lower bound on the randomized communication complexity of finding an ε-approximate Nash equilibrium (for constant ε>0) in a two-player N×N game.

SODA Conference 2017 Conference Paper

Combinatorial Prophet Inequalities

• Aviad Rubinstein
• Sahil Singla 0001

We introduce a novel framework of Prophet Inequalities for combinatorial valuation functions. For a ( n on-monotone) submodular objective function over an arbitrary matroid feasibility constraint, we give an O (1)-competitive algorithm. For a monotone subadditive objective function over an arbitrary downward- closed feasibility constraint, we give an O (log n log 2 r)- competitive algorithm (where r is the cardinality of the largest feasible subset). Inspired by the proof of our subadditive prophet inequality, we also obtain an O (log n · log 2 r)-competitive algorithm for the Secretary Problem with a monotone subadditive objective function subject to an arbitrary downward-closed feasibility constraint. Even for the special case of a cardinality feasibility constraint, our algorithm circumvents an lower bound by Bateni, Hajiaghayi, and Zadimoghaddam [10] in a restricted query model. En route to our submodular prophet inequality, we prove a technical result of independent interest: we show a variant of the Correlation Gap Lemma [14, 1] for nonmonotone submodular functions.

STOC Conference 2017 Conference Paper

Communication complexity of approximate Nash equilibria

• Yakov Babichenko
• Aviad Rubinstein

For a constant ϵ, we prove a ( N ) lower bound on the (randomized) communication complexity of ϵ-Nash equilibrium in two-player N x N games. For n -player binary-action games we prove an exp( n ) lower bound for the (randomized) communication complexity of (ϵ,ϵ)-weak approximate Nash equilibrium, which is a profile of mixed actions such that at least (1-ϵ)-fraction of the players are ϵ-best replying.

FOCS Conference 2017 Conference Paper

Distributed PCP Theorems for Hardness of Approximation in P

• Amir Abboud
• Aviad Rubinstein
• R. Ryan Williams

We present a new distributed model of probabilistically checkable proofs (PCP). A satisfying assignment x ∈ {0, 1} n to a CNF formula φ is shared between two parties, where Alice knows x 1, .. ., x n/2, Bob knows x n/2+1, .. ., xn, and both parties know φ. The goal is to have Alice and Bob jointly write a PCP that x satisfies φ, while exchanging little or no information. Unfortunately, this model as-is does not allow for nontrivial query complexity. Instead, we focus on a non-deterministic variant, where the players are helped by Merlin, a third party who knows all of x. Using our framework, we obtain, for the first time, PCP-like reductions from the Strong Exponential Time Hypothesis (SETH) to approximation problems in P. In particular, under SETH we show that there are no trulysubquadratic approximation algorithms for Maximum Inner Product over {0, 1}-vectors, LCS Closest Pair over permutations, Approximate Partial Match, Approximate Regular Expression Matching, and Diameter in Product Metric. All our inapproximability factors are nearly-tight. In particular, for the first three problems we obtain nearly-polynomial factors of 2 (log n) 1-o(1); only (1+o(1))-factor lower bounds (under SETH) were known before. As an additional feature of our reduction, we obtain new SETH lower bounds for the exact “monochromatic” Closest Pair problem in the Euclidean, Manhattan, and Hamming metrics.

SODA Conference 2017 Conference Paper

ETH Hardness for Densest- k -Subgraph with Perfect Completeness

• Mark Braverman
• Young Kun-Ko
• Aviad Rubinstein
• Omri Weinstein

We show that, assuming the (deterministic) Exponential Time Hypothesis, distinguishing between a graph with an induced k -clique and a graph in which all k -subgraphs have density at most 1 - ∊, requires time. Our result essentially matches the quasi-polynomial algorithms of Feige and Seltser [FS97] and Barman [Bar15] for this problem, and is the first one to rule out an additive PTAS for Densest k -Subgraph. We further strengthen this result by showing that our lower bound continues to hold when, in the soundness case, even subgraphs smaller by a near-polynomial factor are assumed to be at most (1 - ∊)-dense. Our reduction is inspired by recent applications of the “birthday repetition” technique [AIM14, BKW15]. Our analysis relies on information theoretical machinery and is similar in spirit to analyzing a parallel repetition of two- prover games in which the provers may choose to answer some challenges multiple times, while completely ignoring other challenges.

SODA Conference 2017 Conference Paper

Sorting from Noisier Samples

• Aviad Rubinstein
• Shai Vardi

We study the problem of constructing an order over a set of elements given noisy samples. We consider two models for generating the noisy samples; in both, the distribution of samples is induced by an unknown state of nature: a permutation ρ. In Mallow's model, r permutations n i are generated independently from p, each with probability proportional to e −ßd K (ρ, πί), where d K (p, π i ) is the Kemeny distance between ρ and n i - the number of pairs they order differently. In the noisy comparisons model, we are given a tournament, generated from ρ as follows: if i is before j in p, then with probability 1/2 + γ, the edge between them is oriented from i to j. Both of these problems were studied by Braverman and Mossel [7]; they showed how to construct a maximum-likelihood permutation when the noise parameter (ß or γ, respectively) is constant. In this work, we obtain algorithms that work in the presence of stronger noise or respectively). In Mallow's model, our algorithm works for a relaxed solution concept: likelier than nature. That is, rather than requiring that our output maximizes the likelihood over the entire domain, we guarantee that the likelihood of our output is, w. h. p. , greater than or equal to that of the true state of nature (p). An interesting feature of our algorithm is that it handles noise by adding more noise.

STOC Conference 2017 Conference Paper

The limitations of optimization from samples

• Eric Balkanski
• Aviad Rubinstein
• Yaron Singer

In this paper we consider the following question: can we optimize objective functions from the training data we use to learn them? We formalize this question through a novel framework we call optimization from samples (OPS). In OPS, we are given sampled values of a function drawn from some distribution and the objective is to optimize the function under some constraint. While there are interesting classes of functions that can be optimized from samples, our main result is an impossibility. We show that there are classes of functions which are statistically learnable and optimizable, but for which no reasonable approximation for optimization from samples is achievable. In particular, our main result shows that there is no constant factor approximation for maximizing coverage functions under a cardinality constraint using polynomially-many samples drawn from any distribution. We also show tight approximation guarantees for maximization under a cardinality constraint of several interesting classes of functions including unit-demand, additive, and general monotone submodular functions, as well as a constant factor approximation for monotone submodular functions with bounded curvature.

STOC Conference 2016 Conference Paper

Beyond matroids: secretary problem and prophet inequality with general constraints

• Aviad Rubinstein

We study generalizations of the ``Prophet Inequality'' and ``Secretary Problem'', where the algorithm is restricted to an arbitrary downward-closed set system. For 0,1 values, we give O(n)-competitive algorithms for both problems. This is close to the Omega(n/log n) lower bound due to Babaioff, Immorlica, and Kleinberg. For general values, our results translate to O(log(n) log(r))-competitive algorithms, where r is the cardinality of the largest feasible set. This resolves (up to the O(loglog(n) log(r)) factor) an open question posed to us by Bobby Kleinberg.

SODA Conference 2016 Conference Paper

Locally Adaptive Optimization: Adaptive Seeding for Monotone Submodular Functions

• Ashwinkumar Badanidiyuru
• Christos H. Papadimitriou
• Aviad Rubinstein
• Lior Seeman
• Yaron Singer

The Adaptive Seeding problem is an algorithmic challenge motivated by influence maximization in social networks: One seeks to select among certain accessible nodes in a network, and then select, adaptively, among neighbors of those nodes as they become accessible in order to maximize a global objective function. More generally, adaptive seeding is a stochastic optimization framework where the choices in the first stage affect the realizations in the second stage, over which we aim to optimize. Our main result is a (1 – 1/ e ) 2 -approximation for the adaptive seeding problem for any monotone submodular function. While adaptive policies are often approximated via non-adaptive policies, our algorithm is based on a novel method we call locally-adaptive policies. These policies combine a non-adaptive global structure, with local adaptive optimizations. This method enables the (1–1/ e ) 2 -approximation for general monotone submodular functions and circumvents some of the impossibilities associated with non-adaptive policies. We also introduce a fundamental problem in submodular optimization that may be of independent interest: given a ground set of elements where every element appears with some small probability, find a set of expected size at most k that has the highest expected value over the realization of the elements. We show a surprising result: there are classes of monotone submodular functions (including coverage) that can be approximated almost optimally as the probability vanishes. For general monotone submodular functions we show via a reduction from P lanted -C lique that approximations for this problem are not likely to be obtainable. This optimization problem is an important tool for adaptive seeding via non-adaptive policies, and its hardness motivates the introduction of locally-adaptive policies we use in the main result.

SODA Conference 2016 Conference Paper

On the Complexity of Dynamic Mechanism Design

• Christos H. Papadimitriou
• George Pierrakos
• Christos-Alexandros Psomas
• Aviad Rubinstein

FOCS Conference 2016 Conference Paper

Settling the Complexity of Computing Approximate Two-Player Nash Equilibria

• Aviad Rubinstein

We prove that there exists a constant ε > 0 such that, assuming the Exponential Time Hypothesis for PPAD, computing an ε-approximate Nash equilibrium in a two-player (n × n) game requires quasi-polynomial time, nlog1-o(1) n. This matches (up to the o(1) term) the algorithm of Lipton, Markakis, and Mehta [54]. Our proof relies on a variety of techniques from the study of probabilistically checkable proofs (PCP), this is the first time that such ideas are used for a reduction between problems inside PPAD. En route, we also prove new hardness results for computing Nash equilibria in games with many players. In particular, we show that computing an ε-approximate Nash equilibrium in a game with n players requires 2Ω(n) oracle queries to the payoff tensors. This resolves an open problem posed by Hart and Nisan [43], Babichenko [13], and Chen et al. [28]. In fact, our results for n-player games are stronger: they hold with respect to the (ε, δ)-WeakNash relaxation recently introduced by Babichenko et al. [15].

NeurIPS Conference 2016 Conference Paper

The Power of Optimization from Samples

• Eric Balkanski
• Aviad Rubinstein
• Yaron Singer

We consider the problem of optimization from samples of monotone submodular functions with bounded curvature. In numerous applications, the function optimized is not known a priori, but instead learned from data. What are the guarantees we have when optimizing functions from sampled data? In this paper we show that for any monotone submodular function with curvature c there is a (1 - c)/(1 + c - c^2) approximation algorithm for maximization under cardinality constraints when polynomially-many samples are drawn from the uniform distribution over feasible sets. Moreover, we show that this algorithm is optimal. That is, for any c < 1, there exists a submodular function with curvature c for which no algorithm can achieve a better approximation. The curvature assumption is crucial as for general monotone submodular functions no algorithm can obtain a constant-factor approximation for maximization under a cardinality constraint when observing polynomially-many samples drawn from any distribution over feasible sets, even when the function is statistically learnable.

STOC Conference 2015 Conference Paper

Inapproximability of Nash Equilibrium

• Aviad Rubinstein

We prove that finding an ε-approximate Nash equilibrium is PPAD-complete for constant ε and a particularly simple class of games: polymatrix, degree 3 graphical games, in which each player has only two actions. As corollaries, we also prove similar inapproximability results for Bayesian Nash equilibrium in a two-player incomplete information game with a constant number of actions, for relative ε-Nash equilibrium in a two-player game, for market equilibrium in a non-monotone market, for the generalized circuit problem defined by Chen et al. [4], and for approximate competitive equilibrium from equal incomes with indivisible goods.

SODA Conference 2015 Conference Paper

Robust Probabilistic Inference

• Yishay Mansour
• Aviad Rubinstein
• Moshe Tennenholtz

Robust probabilistic inference is an extension of probabilistic inference, where some of the observations are adversarially corrupted. We model it as a zero-sum game between the adversary, who can select a modification rule, and the predictor, who wants to accurately predict the state of nature. Given a black-box access to a Bayesian inference in the classic (adversary-free) setting, our near optimal policy runs in polynomial time in the number of observations and the number of possible modification rules.

FOCS Conference 2014 Conference Paper

Satisfiability and Evolution

• Adi Livnat
• Christos H. Papadimitriou
• Aviad Rubinstein
• Gregory Valiant
• Andrew Wan

We show that, if truth assignments on n variables reproduce through recombination so that satisfaction of a particular Boolean function confers a small evolutionary advantage, then a polynomially large population over polynomially many generations (polynomial in n and the inverse of the initial satisfaction probability) will end up almost certainly consisting exclusively of satisfying truth assignments. We argue that this theorem sheds light on the problem of the evolution of complex adaptations.