72 citations · 399 across the 60 of their papers we have counts for
4 papers · 2 filters
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…
Settling the query complexity of non-adaptive junta testing
Xi Chen, Rocco A. Servedio, Li-Yang Tan +2
We prove that any non-adaptive algorithm that tests whether an unknown Boolean function is a -junta or -far from every -junta must make $\widet…
Fooling intersections of low-weight halfspaces
Rocco A. Servedio, Li-Yang Tan
A weight- halfspace is a Boolean function sign where each is an integer in We give an explicit pseudorandom gene…