A. Rubinstein

activity

20122024

most citedNear-Linear Time Insertion-Deletion Codes and (1+

ε

)-Approximating Edit Distance via Indexing

20 citations · 95 across the 39 of their papers we have counts for

collaborators

Showing 2016 · cs.CCShow all

2 papers · 2 filters

cs.CC2016★ 4 cited

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 $G = (V, E)$ , a subset $S \subseteq V$ is an $(α, β)$ -…

cs.CC2016

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 (nXn) game r…