72 citations · 399 across the 60 of their papers we have counts for
8 papers · 1 filter
Density estimation for shift-invariant multidimensional distributions
Anindya De, Philip M. Long, Rocco A. Servedio
We study density estimation for classes of shift-invariant distributions over . A multidimensional distribution is "shift-invariant" if, roughly speaking, it is close…
Learning sparse mixtures of rankings from noisy information
Anindya De, Ryan O'Donnell, Rocco Servedio
We study the problem of learning an unknown mixture of rankings over elements, given access to noisy samples drawn from the unknown mixture. We consider a range of differen…
Fooling Polytopes
Ryan O'Donnell, Rocco A. Servedio, Li-Yang Tan
We give a pseudorandom generator that fools -facet polytopes over with seed length . The previous best seed length had superlinear…
Learning Sums of Independent Random Variables with Sparse Collective Support
Anindya De, Philip M. Long, Rocco A. Servedio
We study the learnability of sums of independent integer random variables given a bound on the size of the union of their supports. For , a sum…
Luby--Veličković--Wigderson revisited: Improved correlation bounds and pseudorandom generators for depth-two circuits
Rocco A. Servedio, Li-Yang Tan
We study correlation bounds and pseudorandom generators for depth-two circuits that consist of a -gate (computing an arbitrary symmetric function) or -g…
Distribution-free Junta Testing
Xi Chen, Zhengyang Liu, Rocco A. Servedio +2
We study the problem of testing whether an unknown -variable Boolean function is a -junta in the distribution-free property testing model, where the distance between function…
Improved pseudorandom generators from pseudorandom multi-switching lemmas
Rocco A. Servedio, Li-Yang Tan
We give the best known pseudorandom generators for two touchstone classes in unconditional derandomization: an -PRG for the class of size- depth- …
Deterministic search for CNF satisfying assignments in almost polynomial time
Rocco A. Servedio, Li-Yang Tan
We consider the fundamental derandomization problem of deterministically finding a satisfying assignment to a CNF formula that has many satisfying assignments. We give a determinis…