72 citations · 399 across the 60 of their papers we have counts for
73 papers
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…
Testing Convex Truncation
Anindya De, Shivam Nadimpalli, Rocco A. Servedio
We study the basic statistical problem of testing whether normally distributed -dimensional data has been truncated, i.e. altered by only retaining points that lie in some unkno…
Approximate Trace Reconstruction from a Single Trace
Xi Chen, Anindya De, Chin Ho Lee +2
The well-known trace reconstruction problem is the problem of inferring an unknown source string from independent "traces", i.e. copies of that have been corr…
Near-Optimal Statistical Query Lower Bounds for Agnostically Learning Intersections of Halfspaces with Gaussian Marginals
Daniel Hsu, Clayton Sanford, Rocco Servedio +1
We consider the well-studied problem of learning intersections of halfspaces under the Gaussian distribution in the challenging \emph{agnostic learning} model. Recent work of Diako…
The perils of being unhinged: On the accuracy of classifiers minimizing a noise-robust convex loss
Philip M. Long, Rocco A. Servedio
Van Rooyen et al. introduced a notion of convex loss functions being robust to random classification noise, and established that the "unhinged" loss function is robust in this sens…
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^*…