16 citations · 47 across the 9 of their papers we have counts for
Showing cs.CCShow all
2 papers · 1 filter
cs.CC2014
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…
cs.CC2014★ 16 cited
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 $\…