72 citations · 399 across the 60 of their papers we have counts for
8 papers · 1 filter
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^*…
Convex Influences
Anindya De, Shivam Nadimpalli, Rocco A. Servedio
We introduce a new notion of influence for symmetric convex sets over Gaussian space, which we term "convex influence". We show that this new notion of influence shares many of the…
Near-Optimal Average-Case Approximate Trace Reconstruction from Few Traces
Xi Chen, Anindya De, Chin Ho Lee +2
In the standard trace reconstruction problem, the goal is to \emph{exactly} reconstruct an unknown source string from independent "traces", which are cop…
Approximating Sumset Size
Anindya De, Shivam Nadimpalli, Rocco A. Servedio
Given a subset of the -dimensional Boolean hypercube , the sumset is the set where addition is in . Sumsets pla…
Fourier growth of structured -polynomials and applications
Jarosław Błasiok, Peter Ivanov, Yaonan Jin +3
We analyze the Fourier growth, i.e. the Fourier weight at level (denoted ), of various well-studied classes of "structured" -polynomials. This stud…
Fooling Gaussian PTFs via Local Hyperconcentration
Ryan O'Donnell, Rocco A. Servedio, Li-Yang Tan +1
We give a pseudorandom generator that fools degree- polynomial threshold functions over -dimensional Gaussian space with seed length . All previ…
On the Approximation Power of Two-Layer Networks of Random ReLUs
Daniel Hsu, Clayton Sanford, Rocco A. Servedio +1
This paper considers the following question: how well can depth-two ReLU networks with randomly initialized bottom-level weights represent smooth functions? We give near-matching u…