3 papers
cs.CC2026
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…
cs.CC2026
Quadratic Speedup for Computing Contraction Fixed Points
Xi Chen, Yuhao Li, Mihalis Yannakakis
We study the problem of finding an -fixed point of a contraction map under both the -norm and the -norm. For both norms, we give a…
cs.CC2024
Relative-error monotonicity testing
Xi Chen, Anindya De, Yizhi Huang +4
The standard model of Boolean function property testing is not well suited for testing functions which have few satisfying assignments, since every such function…