8 citations · 27 across the 13 of their papers we have counts for
5 papers · 1 filter
Average-Case Subset Balancing Problems
Xi Chen, Yaonan Jin, Tim Randolph +1
Given a set of input integers, the Equal Subset Sum problem asks us to find two distinct subsets with the same sum. In this paper we present an algorithm that runs in time $O^*…
Distribution-free Junta Testing
Xi Chen, Zhengyang Liu, Rocco A. Servedio +2
We study the problem of testing whether an unknown -variable Boolean function is a -junta in the distribution-free property testing model, where the distance between function…
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…