8 citations · 15 across the 5 of their papers we have counts for
5 papers
Efficient average-case population recovery in the presence of insertions and deletions
Frank Ban, Xi Chen, Rocco A. Servedio +1
Several recent works have considered the \emph{trace reconstruction problem}, in which an unknown source string is transmitted through a probabilistic channel which…
Nearly optimal edge estimation with independent set queries
Xi Chen, Amit Levi, Erik Waingarten
We study the problem of estimating the number of edges of an unknown, undirected graph with access to an independent set oracle. When queried about a subset $S\subseteq…
Boolean Unateness Testing with Adaptive Queries
Xi Chen, Erik Waingarten, Jinyu Xie
We give an adaptive algorithm which tests whether an unknown Boolean function is unate, i.e. every variable of is either non-decreasing or non-…
Sample-based high-dimensional convexity testing
Xi Chen, Adam Freilich, Rocco A. Servedio +1
In the problem of high-dimensional convexity testing, there is an unknown set which is promised to be either convex or -far from every conve…
Adaptivity is exponentially powerful for testing monotonicity of halfspaces
Xi Chen, Rocco A. Servedio, Li-Yang Tan +1
We give a -query adaptive algorithm for testing whether an unknown Boolean function , which is promised to be a halfspace, i…