3 papers
cs.CC2026
Tarski Fixed Points in Quasi-FPT Queries
Xi Chen, Ruiquan Gao, Yuhao Li +2
We study the query complexity of finding a Tarski fixed point over . Previous work has left a large gap between and . We show tha…
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 μ…