All reports by Author Thomas Steinke:

__
TR14-166
| 8th December 2014
__

Mark Bun, Thomas Steinke#### Weighted Polynomial Approximations: Limits for Learning and Pseudorandomness

__
TR14-076
| 27th May 2014
__

Thomas Steinke#### Pseudorandomness and Fourier Growth Bounds for Width 3 Branching Programs

Revisions: 1

__
TR13-086
| 13th June 2013
__

Omer Reingold, Thomas Steinke, Salil Vadhan#### Pseudorandomness for Regular Branching Programs via Fourier Analysis

Revisions: 1

__
TR12-083
| 29th June 2012
__

Thomas Steinke#### Pseudorandomness for Permutation Branching Programs Without the Group Theory

__
TR11-115
| 8th August 2011
__

Varun Kanade, Thomas Steinke#### Learning Hurdles for Sleeping Experts

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 algorithms for agnostically learning halfspaces, as well as pseudorandom generators for halfspaces. In this work, we investigate the limits of these techniques by proving inapproximability results for ... more >>>

Thomas Steinke

We present an explicit pseudorandom generator for oblivious, read-once, width-$3$ branching programs, which can read their input bits in any order. The generator has seed length $\tilde{O}( \log^3 n ).$ The previously best known seed length for this model is $n^{1/2+o(1)}$ due to Impagliazzo, Meka, and Zuckerman (FOCS '12). Our ... more >>>

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 length is $O(\log^2 n)$, where $n$ is the length of the branching program. The previous best seed length known for this model was $n^{1/2+o(1)}$, ... more >>>

Thomas Steinke

We exhibit an explicit pseudorandom generator that stretches an $O \left( \left( w^4 \log w + \log (1/\varepsilon) \right) \cdot \log n \right)$-bit random seed to $n$ pseudorandom bits that cannot be distinguished from truly random bits by a permutation branching program of width $w$ with probability more than $\varepsilon$. ... more >>>

Varun Kanade, Thomas Steinke

We study the online decision problem where the set of available actions varies over time, also called the sleeping experts problem. We consider the setting where the performance comparison is made with respect to the best ordering of actions in hindsight. In this paper, both the payoff function and the ... more >>>