Publications

2025

1. FOCS 2025

   An Improved Greedy Approximation for (Metric) k-Means

   Moses Charikar, Vincent Cohen-Addad, Ruiquan Gao, Fabrizio Grandoni, Euiwoong Lee, and Ernest van Wijland

   Proceedings of the 66th IEEE Symposium on Foundations of Computer Science (to appear), 2025

   Abs

   Clustering is a basic task in data analysis and machine learning, and the optimization of clustering objectives are well-studied optimization problems; amongst these, the \(k\)-Means objective is arguably the most well known. Given a collection of points in a metric space, the goal is to partition them into \(k\) clusters, each with an associated center, so as to minimize the sum of squared distances of points to their cluster centers. In this paper, we present a polynomial-time \(3+2\sqrt2+ε<5.83\)-approximation algorithm for \(k\)-Means in general metrics. This substantially improves on the current-best \((9+ε)\)-approximation in [Ahmadian, Norouzi-Fard, Svensson, Ward - FOCS’17, SICOMP’20], and even slightly improves on the \(5.92\)-approximation in [Cohen-Addad, Esfandiari, Mirrokni, Narayanan - STOC’22] for the Euclidean special case. A natural approach for \(k\)-Means is to leverage Lagrangian Multiplier Preserving (LMP) approximations for the facility location problem. The previous best results for \(k\)-Means build upon an adaptation of an LMP \(3\)-approximation for facility location with metric connection costs in [Jain, Vazirani - J.ACM’01] based on a primal-dual method, rather than on the improved LMP greedy \(2\)-approximation for the same problem in [Jain, Mahdian, Markakis, Saberi, Vazirani - J.ACM’03]. The barrier to using the improved LMP algorithm was that no adaptation of this algorithm and its analysis to the case of squared metric connection costs was known (since squared distances violate triangle inequality). Our main contribution is overcoming this barrier by providing such an adaptation. This new LMP approximation algorithm is then combined with the framework recently introduced in [Cohen-Addad, Grandoni, Lee, Schwiegelshohn, Svensson - STOC’25] for the related (metric) \(k\)-Median problem.

2. FOCS 2025

   High-to-Low Dimensional PPA-completeness: Borsuk-Ulam, Tucker, Consensus Halving, and Ham Sandwich

   Ruiquan Gao, Alexandros Hollender, and Aviad Rubinstein

   Proceedings of the 66th IEEE Symposium on Foundations of Computer Science (to appear), 2025

   Abs Slides

   The Borsuk-Ulam theorem states that every continuous odd function \(f: S^n \to R^n\) must have a zero, i.e., an \(x ∈S^n\) such that \(f(x) = 0\). While such a zero is guaranteed to exist, finding it is known to be computationally intractable: it is \({\sf PPA}\)-complete already for \(n=2\). In this work, we show that the problem remains just as hard even if the function is mapping from a higher to a lower dimensional space. Namely, we prove that it is \({\sf PPA}\)-complete to find a zero of \(f: S^k \to R^n\) for any constants \(k ≥n ≥2\). This result has very appealing consequences for other flagship \({\sf PPA}\)-complete problems such as Tucker, Consensus Halving, and Ham Sandwich. For example, in the Consensus Halving problem from fair division, we show that finding a partition that satisfies three agents with monotone valuations is \({\sf PPA}\)-complete, even if we allow any arbitrarily large constant number of cuts.

2024

1. FOCS 2024

   Hardness of Approximate Sperner and Applications to Envy-Free Cake Cutting

   Ruiquan Gao, Mohammad Roghani, Aviad Rubinstein, and Amin Saberi

   Proceedings of the 65th IEEE Symposium on Foundations of Computer Science, 2024

   Abs PDF Slides

   Given a so called “Sperner coloring” of a triangulation of the \(D\)-dimensional simplex, Sperner’s lemma guarantees the existence of a rainbow simplex, i.e. a simplex colored by all \(D+1\) colors. However, finding a rainbow simplex was the first problem to be proven \({\sf PPAD}\)-complete in Papadimitriou’s classical paper introducing the class \({\sf PPAD}\) (1994). In this paper, we prove that the problem does not become easier if we relax “all \(D+1\) colors” to allow some fraction of missing colors: in fact, for any constant \(D\), finding even a simplex with just three colors remains \({\sf PPAD}\)-complete! Our result has an interesting application for the envy-free cake cutting from fair division. It is known that if agents value pieces of cake using general continuous functions satisfying a simple boundary condition (“a non-empty piece is better than an empty piece of cake”), there exists an envy-free allocation with connected pieces. We show that for any constant number of agents it is \({\sf PPAD}\)-complete to find an allocation –even using any constant number of possibly disconnected pieces– that makes just three agents envy-free. Our results extend to super-constant dimension, number of agents, and number of pieces, as long as they are asymptotically bounded by any \((\log ε^{-1})^{1-Ω(1)}\), where \(ε\) is the precision parameter (side length for Sperner and approximate envy-free for cake cutting).

2. STOC 2024

   Parallel Sampling via Counting

   Nima Anari, Ruiquan Gao, and Aviad Rubinstein

   Proceedings of the 56th Annual ACM Symposium on Theory of Computing, 2024

   Abs PDF Slides

   We show how to use parallelization to speed up sampling from an arbitrary distribution on a product space \([q]^n\), given oracle access to counting queries: \(P[X_S=y_S]\) for any \(S⊆[n]\) and \(y_S ∈[q]^S\). Our algorithm takes \(O(n^{2/3} ⋅{\rm polylog}(n,q))\) parallel time, to the best of our knowledge, the first sublinear in \(n\) runtime for arbitrary distributions. We complement our positive result by showing a lower bound of \(Ω((n/\log n)^{1/3})\) for the runtime of any parallel sampling algorithm making at most \({\rm poly}(n)\) queries to the counting oracle, even for \(q=2\).

3. SODA 2024

   Improved Approximations for Ultrametric Violation Distance

   Moses Charikar, and Ruiquan Gao

   Proceedings of the 2024 ACM-SIAM Symposium on Discrete Algorithms, 2024

   Abs PDF Slides

   We study the Ultrametric Violation Distance problem introduced by Cohen-Addad, Fan, Lee, and Mesmay [FOCS, 2022]. Given pairwise distances \(x\) as input, the goal is to modify the minimum number of distances so as to make it a valid ultrametric. In other words, this is the problem of fitting an ultrametric to given data, where the quality of the fit is measured by the \(\ell_0\) norm of the error; variants of the problem for the \(\ell_∞\) and \(\ell_1\) norms are well-studied in the literature. Our main result is a \(5\)-approximation algorithm for Ultrametric Violation Distance, improving the previous best large constant factor (\(≥1000\)) approximation algorithm. We give an \(O(\min(L,\log n))\) -approximation algorithm for weighted Ultrametric Violation Distance where the weights satisfy triangle inequality and \(L\) is the number of distinct values in the input. We also give a \(16\)-approximation algorithm for the problem on \(k\)-partite graphs, where the input is specified on pairs of vertices that form a complete \(k\)-partite graph. All our results use a unified algorithmic framework with small modifications for the three cases.

2023

1. EC 2023

   Practical algorithms and experimentally validated incentives for equilibrium-based fair division (A-CEEI)

   Eric Budish, Ruiquan Gao, Abraham Othman, Aviad Rubinstein, and Qianfan Zhang

   Proceedings of the 24th ACM Conference on Economics and Computation, 2023

   Abs PDF

   Approximate Competitive Equilibrium from Equal Incomes (A-CEEI) is an equilibrium-based solution concept for fair division of discrete items to agents with combinatorial demands. In theory, it is known that in asymptotically large markets: 1. For incentives, the A-CEEI mechanism is Envy-Free-but-for-Tie-Breaking (EF-TB), which implies that it is Strategyproof-in-the-Large (SP-L). 2. From a computational perspective, computing the equilibrium solution is unfortunately a computationally intractable problem (in the worst-case, assuming \({\sf PPAD}≠{\sf FP}\)). We develop a new heuristic algorithm that outperforms the previous state-of-the-art by multiple orders of magnitude. This new, faster algorithm lets us perform experiments on real-world inputs for the first time. We discover that with real-world preferences, even in a realistic implementation that satisfies the EF-TB and SP-L properties, agents may have surprisingly simple and plausible deviations from truthful reporting of preferences. To this end, we propose a novel strengthening of EF-TB, which dramatically reduces the potential for strategic deviations from truthful reporting in our experiments. A (variant of) our algorithm is now in production: on real course allocation problems it is much faster, has zero clearing error, and has stronger incentive properties than the prior state-of-the-art implementation.

2021

1. FOCS 2021

   Improved Online Correlated Selection

   Ruiquan Gao, Zhongtian He, Zhiyi Huang, Zipei Nie, Bijun Yuan, and Yan Zhong

   Proceedings of the 62nd IEEE Annual Symposium on Foundations of Computer Science, 2021

   Abs Talk PDF

   This paper studies the online correlated selection (OCS) problem. It was introduced by Fahrbach, Huang, Tao, and Zadimoghaddam (2020) to obtain the first edge-weighted online bipartite matching algorithm that breaks the \(0.5\) barrier. Suppose that we receive a pair of elements in each round and immediately select one of them. Can we select with negative correlation to be more effective than independent random selections? Our contributions are threefold. For semi-OCS, which considers the probability that an element remains unselected after appearing in \(k\) rounds, we give an optimal algorithm that minimizes this probability for all \(k\). It leads to \(0.536\)-competitive unweighted and vertex-weighted online bipartite matching algorithms that randomize over only two options in each round, improving the \(0.508\)-competitive ratio by Fahrbach et al. (2020). Further, we develop the first multi-way semi-OCS that allows an arbitrary number of elements with arbitrary masses in each round. As an application, it rounds the Balance algorithm in unweighted and vertex-weighted online bipartite matching and is \(0.593\)-competitive. Finally, we study OCS, which further considers the probability that an element is unselected in an arbitrary subset of rounds. We prove that the optimal "level of negative correlation" is between \(0.167\) and \(0.25\), improving the previous bounds of \(0.109\) and \(1\) by Fahrbach et al. (2020). Our OCS gives a \(0.519\)-competitive edge-weighted online bipartite matching algorithm, improving the previous \(0.508\)-competitive ratio by Fahrbach et al. (2020).