3 papers
cs.CC2023
Gaussian Approximation of Convex Sets by Intersections of Halfspaces
Anindya De, Shivam Nadimpalli, Rocco A. Servedio
We study the approximability of general convex sets in by intersections of halfspaces, where the approximation quality is measured with respect to the standard Gauss…
cs.CC2023
Mildly Exponential Lower Bounds on Tolerant Testers for Monotonicity, Unateness, and Juntas
Xi Chen, Anindya De, Yuhao Li +2
We give the first super-polynomial (in fact, mildly exponential) lower bounds for tolerant testing (equivalently, distance estimation) of monotonicity, unateness, and juntas with a…
cs.CC2023
Testing Junta Truncation
William He, Shivam Nadimpalli
We consider the basic statistical problem of detecting truncation of the uniform distribution on the Boolean hypercube by juntas. More concretely, we give upper and lower bounds on…