4 citations · 10 across the 14 of their papers we have counts for
7 papers · 1 filter
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 optimiza…
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 i…
Near-Optimal Communication Lower Bounds for Approximate Nash Equilibria
Mika Göös, Aviad Rubinstein
We prove an lower bound on the randomized communication complexity of finding an -approximate Nash equilibrium (for constant ) in a two-player game…
Optimal Deterministic Mechanisms for an Additive Buyer
Moshe Babaioff, Noam Nisan, Aviad Rubinstein
We study revenue maximization by deterministic mechanisms for the simplest case for which Myerson's characterization does not hold: a single seller selling two items, with independ…
An Exponential Speedup in Parallel Running Time for Submodular Maximization without Loss in Approximation
Eric Balkanski, Aviad Rubinstein, Yaron Singer
In this paper we study the adaptivity of submodular maximization. Adaptivity quantifies the number of sequential rounds that an algorithm makes when function evaluations can be exe…
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 th…