72 citations · 399 across the 60 of their papers we have counts for
38 papers · 1 filter
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…
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…
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…
Testing noisy linear functions for sparsity
Xue Chen, Anindya De, Rocco A. Servedio
We consider the following basic inference problem: there is an unknown high-dimensional vector , and an algorithm is given access to labeled pairs where…