2 citations · 5 across the 16 of their papers we have counts for
4 papers · 1 filter
Hardness of Approximate Sperner and Applications to Envy-Free Cake Cutting
Ruiquan Gao, Mohammad Roghani, Aviad Rubinstein +1
Given a so called ''Sperner coloring'' of a triangulation of the -dimensional simplex, Sperner's lemma guarantees the existence of a rainbow simplex, i.e. a simplex colored by a…
Parallel Sampling via Counting
Nima Anari, Ruiquan Gao, Aviad Rubinstein
We show how to use parallelization to speed up sampling from an arbitrary distribution on a product space , given oracle access to counting queries: $\mathbb{P}_{X\sim μ…
Approximating Maximum Matching Requires Almost Quadratic Time
Soheil Behnezhad, Mohammad Roghani, Aviad Rubinstein
We study algorithms for estimating the size of maximum matching. This problem has been subject to extensive research. For -vertex graphs, Bhattacharya, Kiss, and Saranurak [FOCS…
The complexity of approximate (coarse) correlated equilibrium for incomplete information games
Binghui Peng, Aviad Rubinstein
We study the iteration complexity of decentralized learning of approximate correlated equilibria in incomplete information games. On the negative side, we prove that in $\mathit{ex…