3 papers
cs.DS2026
Sublinear-query relative-error testing of halfspaces
Xi Chen, Anindya De, Yizhi Huang +3
The relative-error property testing model was introduced in [CDHLNSY24] to facilitate the study of property testing for "sparse" Boolean-valued functions, i.e. ones for which only…
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.DS2025
A Mysterious Connection Between Tolerant Junta Testing and Agnostically Learning Conjunctions
Xi Chen, Shyamal Patel, Rocco A. Servedio
The main conceptual contribution of this paper is identifying a previously unnoticed connection between two central problems in computational learning theory and property testing:…