8 citations · 34 across the 6 of their papers we have counts for
6 papers
Hitting the High Notes: Subset Selection for Maximizing Expected Order Statistics
Aranyak Mehta, Uri Nadav, Alexandros Psomas +1
We consider the fundamental problem of selecting out of random variables in a way that the expected highest or second-highest value is maximized. This question captures sev…
Detecting communities is hard, and counting them is even harder
Aviad Rubinstein
We consider the algorithmic problem of community detection in networks. Given an undirected friendship graph , a subset is an -…
Combinatorial Prophet Inequalities
Aviad Rubinstein, Sahil Singla
We introduce a novel framework of Prophet Inequalities for combinatorial valuation functions. For a (non-monotone) submodular objective function over an arbitrary matroid feasibili…
Computational Complexity of Approximate Nash Equilibrium in Large Games
Aviad Rubinstein
We prove that finding an epsilon-Nash equilibrium in a succinctly representable game with many players is PPAD-hard for constant epsilon. Our proof uses succinct games, i.e. games…
On Simplex Pivoting Rules and Complexity Theory
Ilan Adler, Christos Papadimitriou, Aviad Rubinstein
We show that there are simplex pivoting rules for which it is PSPACE-complete to tell if a particular basis will appear on the algorithm's path. Such rules cannot be the basis of a…
Converting online algorithms to local computation algorithms
Yishay Mansour, Aviad Rubinstein, Shai Vardi +1
We propose a general method for converting online algorithms to local computation algorithms by selecting a random permutation of the input, and simulating running the online algor…