Publications (30)
Combining Traditional Marketing and Viral Marketing with Amphibious Influence Maximization
Wei Chen, Fu Li, Tian Lin +1
An Optimal Approximation for Submodular Maximization under a Matroid Constraint in the Adaptive Complexity Model
Eric Balkanski, Aviad Rubinstein, Yaron Singer
Distributed PCP Theorems for Hardness of Approximation in P
Amir Abboud, Aviad Rubinstein, Ryan Williams
Optimal Deterministic Mechanisms for an Additive Buyer
Moshe Babaioff, Noam Nisan, Aviad Rubinstein
Near-Linear Time Insertion-Deletion Codes and (1+$\varepsilon$)-Approximating Edit Distance via Indexing
Bernhard Haeupler, Aviad Rubinstein, Amirbehshad Shahrasbi
Simple Mechanisms for a Subadditive Buyer and Applications to Revenue Monotonicity
Aviad Rubinstein, S. Matthew Weinberg
Computing exact minimum cuts without knowing the graph
Aviad Rubinstein, Tselil Schramm, S. Matthew Weinberg
Communication complexity of approximate Nash equilibria
Yakov Babichenko, Aviad Rubinstein
Boolean functions whose Fourier transform is concentrated on pairwise disjoint subsets of the input
Aviad Rubinstein, Muli Safra
ETH Hardness for Densest-$k$-Subgraph with Perfect Completeness
Mark Braverman, Young Kun Ko, Aviad Rubinstein +1
Inapproximability of Nash Equilibrium
Aviad Rubinstein
On the Computational Complexity of Optimal Simple Mechanisms
Aviad Rubinstein
On Simplex Pivoting Rules and Complexity Theory
Ilan Adler, Christos Papadimitriou, Aviad Rubinstein
Reducing approximate Longest Common Subsequence to approximate Edit Distance
Aviad Rubinstein, Zhao Song
Combinatorial Prophet Inequalities
Aviad Rubinstein, Sahil Singla
Converting online algorithms to local computation algorithms
Yishay Mansour, Aviad Rubinstein, Shai Vardi +1
Locally Adaptive Optimization: Adaptive Seeding for Monotone Submodular Functions
Ashwinkumar Badanidiyuru, Christos Papadimitriou, Aviad Rubinstein +2
Inapproximability of VC Dimension and Littlestone's Dimension
Pasin Manurangsi, Aviad Rubinstein
Settling the complexity of computing approximate two-player Nash equilibria
Aviad Rubinstein
Hardness of Approximate Nearest Neighbor Search
Aviad Rubinstein
Computational Complexity of Approximate Nash Equilibrium in Large Games
Aviad Rubinstein
Near-Optimal Communication Lower Bounds for Approximate Nash Equilibria
Mika Göös, Aviad Rubinstein
An Exponential Speedup in Parallel Running Time for Submodular Maximization without Loss in Approximation
Eric Balkanski, Aviad Rubinstein, Yaron Singer
99\% Revenue via Enhanced Competition
Michal Feldman, Ophir Friedler, Aviad Rubinstein
On the Worst-Case Approximability of Sparse PCA
Siu On Chan, Dimitris Papailiopoulos, Aviad Rubinstein
The Complexity of Fairness through Equilibrium
Abraham Othman, Christos Papadimitriou, Aviad Rubinstein
Honest signaling in zero-sum games is hard, and lying is even harder
Aviad Rubinstein
Detecting communities is hard, and counting them is even harder
Aviad Rubinstein
The Limitations of Optimization from Samples
Eric Balkanski, Aviad Rubinstein, Yaron Singer
Satisfiability and Evolution
Adi Livnat, Christos Papadimitriou, Aviad Rubinstein +2