12 papers
DNF formulas are efficiently testable with relative error
Xi Chen, William Pires, Toniann Pitassi +1
We give a poly-query algorithm for testing whether an unknown and arbitrary function is an -term DNF, in the challenging relative-error frame…
Model-agnostic distribution recovery in high dimension via Fourier measurements
Xi Chen, Anindya De, Yizhi Huang +3
We study the problem of reconstructing an unknown probability distribution to high accuracy, given noisy information about its low-degree Fourier coefficients. Prior results for th…
Halfspaces are hard to test with relative error
Xi Chen, Anindya De, Yizhi Huang +3
Several recent works [DHLNSY25, CPPS25a, CPPS25b] have studied a model of property testing of Boolean functions under a \emph{relative-error} criterion. In this model, the distance…
Relative-error unateness testing
Xi Chen, Diptaksho Palit, Kabir Peshawaria +3
The model of relative-error property testing of Boolean functions has been the subject of significant recent research effort [CDH+24][CPPS25a][CPPS25b] In this paper we consider th…
Testing Juntas and Junta Subclasses with Relative Error
Xi Chen, William Pires, Toniann Pitassi +1
This papers considers the junta testing problem in a recently introduced ``relative error'' variant of the standard Boolean function property testing model. In relative-error testi…
Relative-error testing of conjunctions and decision lists
Xi Chen, William Pires, Toniann Pitassi +1
We study the relative-error property testing model for Boolean functions that was recently introduced in the work of Chen et al. (SODA 2025). In relative-error testing, the testing…
Lower Bounds for Convexity Testing
Xi Chen, Anindya De, Shivam Nadimpalli +2
We consider the problem of testing whether an unknown and arbitrary set (given as a black-box membership oracle) is convex, versus -far from…
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…
Trace reconstruction from local statistical queries
Xi Chen, Anindya De, Chin Ho Lee +1
The goal of trace reconstruction is to reconstruct an unknown -bit string given only independent random traces of , where a random trace of is obtained by passing …
Testing Sumsets is Hard
Xi Chen, Shivam Nadimpalli, Tim Randolph +2
A subset of the Boolean hypercube is a sumset if for some . Sumsets are central objects of study in add…
Testing Intersecting and Union-Closed Families
Xi Chen, Anindya De, Yuhao Li +2
Inspired by the classic problem of Boolean function monotonicity testing, we investigate the testability of other well-studied properties of combinatorial finite set systems, speci…
Subset Sum in Time
Xi Chen, Yaonan Jin, Tim Randolph +1
A major goal in the area of exact exponential algorithms is to give an algorithm for the (worst-case) -input Subset Sum problem that runs in time for some const…