72 citations · 399 across the 60 of their papers we have counts for
4 papers · 2 filters
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…