72 citations · 399 across the 60 of their papers we have counts for
5 papers · 1 filter
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…
Sharp bounds for population recovery
Anindya De, Ryan O'Donnell, Rocco Servedio
The population recovery problem is a basic problem in noisy unsupervised learning that has attracted significant research attention in recent years [WY12,DRWY12, MS13, BIMP13, LZ15…