4 papers
Distribution-Free Halfspace Testing with Samples
Xi Chen, Renato Ferreira Pinto, Nathaniel Harms +2
We prove a tight lower bound on the number of samples required for testing halfspaces over , in the distribution-free sample-based model where the underlying…
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…
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]. Additionall…
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:…