16 citations · 16 across the 3 of their papers we have counts for
3 papers
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.CR2014
Interactive Fingerprinting Codes and the Hardness of Preventing False Discovery
Thomas Steinke, Jonathan Ullman
We show an essentially tight bound on the number of adaptively chosen statistical queries that a computationally efficient algorithm can answer accurately given samples from an…
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 $\…