All reports by Author William Hoza:

__
TR19-149
| 4th November 2019
__

Dean Doron, Pooya Hatami, William Hoza#### Log-Seed Pseudorandom Generators via Iterated Restrictions

__
TR18-183
| 5th November 2018
__

Dean Doron, Pooya Hatami, William Hoza#### Near-Optimal Pseudorandom Generators for Constant-Depth Read-Once Formulas

Revisions: 2

__
TR18-063
| 5th April 2018
__

William Hoza, David Zuckerman#### Simple Optimal Hitting Sets for Small-Success $\mathbf{RL}$

Revisions: 1

__
TR16-172
| 3rd November 2016
__

William Hoza, Adam Klivans#### Preserving Randomness for Adaptive Algorithms

Revisions: 4

Dean Doron, Pooya Hatami, William Hoza

There are only a few known general approaches for constructing explicit pseudorandom generators (PRGs). The ``iterated restrictions'' approach, pioneered by Ajtai and Wigderson [AW89], has provided PRGs with seed length $\mathrm{polylog} n$ or even $\tilde{O}(\log n)$ for several restricted models of computation. Can this approach ever achieve the optimal seed ... more >>>

Dean Doron, Pooya Hatami, William Hoza

We give an explicit pseudorandom generator (PRG) for constant-depth read-once formulas over the basis $\{\wedge, \vee, \neg\}$ with unbounded fan-in. The seed length of our PRG is $\widetilde{O}(\log(n/\varepsilon))$. Previously, PRGs with near-optimal seed length were known only for the depth-2 case (Gopalan et al. FOCS '12). For a constant depth ... more >>>

William Hoza, David Zuckerman

We give a simple explicit hitting set generator for read-once branching programs of width $w$ and length $r$ with known variable order. Our generator has seed length $O\left(\frac{\log(wr) \log r}{\max\{1, \log \log w - \log \log r\}} + \log(1/\varepsilon)\right)$. This seed length improves on recent work by Braverman, Cohen, and ... more >>>

William Hoza, Adam Klivans

We introduce the concept of a randomness steward, a tool for saving random bits when executing a randomized estimation algorithm $\mathrm{Est}$ on many adaptively chosen inputs. For each execution, the chosen input to $\mathrm{Est}$ remains hidden from the steward, but the steward chooses the randomness of $\mathrm{Est}$ and, crucially, is ... more >>>