20 citations · 95 across the 39 of their papers we have counts for
5 papers · 1 filter
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…
Communication complexity of approximate Nash equilibria
Yakov Babichenko, Aviad Rubinstein
For a constant , we prove a poly(N) lower bound on the (randomized) communication complexity of -Nash equilibrium in two-player NxN games. For n-player binary-action games we…
Settling the complexity of computing approximate two-player Nash equilibria
Aviad Rubinstein
We prove that there exists a constant such that, assuming the Exponential Time Hypothesis for PPAD, computing an -approximate Nash equilibrium in a two-player (nXn) game r…
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 giv…