138 citations · 191 across the 22 of their papers we have counts for
31 papers
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…
The Mystery Deepens: On the Query Complexity of Tarski Fixed Points
Xi Chen, Yuhao Li, Mihalis Yannakakis
We give an -query algorithm for finding a Tarski fixed point over the -dimensional lattice , matching the lower bound of [EPRY20]. Additionally…
The Fairness-Quality Trade-off in Clustering
Rashida Hakim, Ana-Andreea Stoica, Christos H. Papadimitriou +1
Fairness in clustering has been considered extensively in the past; however, the trade-off between the two objectives -- e.g., can we sacrifice just a little in the quality of the…
Computing a Fixed Point of Contraction Maps in Polynomial Queries
Xi Chen, Yuhao Li, Mihalis Yannakakis
We give an algorithm for finding an -fixed point of a contraction map under the -norm with query complexity .
Smoothed Complexity of SWAP in Local Graph Partitioning
Xi Chen, Chenghao Guo, Emmanouil-Vasileios Vlatakis-Gkaragkounis +1
We give the first quasipolynomial upper bound for the smoothed complexity of the SWAP algorithm for local Graph Partitioning (also known as Bisection Width…
The Smoothed Complexity of Policy Iteration for Markov Decision Processes
Miranda Christ, Mihalis Yannakakis
We show subexponential lower bounds (i.e., ) on the smoothed complexity of the classical Howard's Policy Iteration algorithm for Markov Decision Processes. The bounds h…