37 citations · 101 across the 43 of their papers we have counts for
5 papers · 1 filter
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…
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…
Non-Malleable Codes for Small-Depth Circuits
Marshall Ball, Dana Dachman-Soled, Siyao Guo +2
We construct efficient, unconditional non-malleable codes that are secure against tampering functions computed by small-depth circuits. For constant-depth circuits of polynomial si…
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…