72 citations · 394 across the 35 of their papers we have counts for
4 papers · 1 filter
Pseudorandomness for Read-Once, Constant-Depth Circuits
Sitan Chen, Thomas Steinke, Salil Vadhan
For Boolean functions computed by read-once, depth- circuits with unbounded fan-in over the de Morgan basis, we present an explicit pseudorandom generator with seed length $\til…
Weighted Polynomial Approximations: Limits for Learning and Pseudorandomness
Mark Bun, Thomas Steinke
Polynomial approximations to boolean functions have led to many positive results in computer science. In particular, polynomial approximations to the sign function underly algorith…
Pseudorandomness and Fourier Growth Bounds for Width 3 Branching Programs
Thomas Steinke, Salil Vadhan, Andrew Wan
We present an explicit pseudorandom generator for oblivious, read-once, width- branching programs, which can read their input bits in any order. The generator has seed length $\…
Pseudorandomness for Regular Branching Programs via Fourier Analysis
Omer Reingold, Thomas Steinke, Salil Vadhan
We present an explicit pseudorandom generator for oblivious, read-once, permutation branching programs of constant width that can read their input bits in any order. The seed lengt…