2 papers
cs.CC2024
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…
cs.DS2024
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…