All reports by Author William Hoza:

__
TR23-176
| 15th November 2023
__

William Hoza#### A Technique for Hardness Amplification Against $\mathrm{AC}^0$

Revisions: 2

__
TR23-114
| 8th August 2023
__

Lijie Chen, William Hoza, Xin Lyu, Avishay Tal, Hongxun Wu#### Weighted Pseudorandom Generators via Inverse Analysis of Random Walks and Shortcutting

__
TR23-019
| 2nd March 2023
__

Pooya Hatami, William Hoza#### Theory of Unconditional Pseudorandom Generators

Revisions: 2

__
TR22-121
| 27th August 2022
__

William Hoza#### Recent Progress on Derandomizing Space-Bounded Computation

Revisions: 1

__
TR22-087
| 8th June 2022
__

Pooya Hatami, William Hoza, Avishay Tal, Roei Tell#### Depth-$d$ Threshold Circuits vs. Depth-$(d + 1)$ AND-OR Trees

Revisions: 1

__
TR21-048
| 27th March 2021
__

William Hoza#### Better Pseudodistributions and Derandomization for Space-Bounded Computation

Revisions: 1

__
TR21-002
| 8th January 2021
__

Pooya Hatami, William Hoza, Avishay Tal, Roei Tell#### Fooling Constant-Depth Threshold Circuits

Revisions: 1

__
TR20-138
| 9th September 2020
__

William Hoza, Edward Pyne, Salil Vadhan#### Pseudorandom Generators for Unbounded-Width Permutation Branching Programs

Revisions: 1

__
TR20-016
| 17th February 2020
__

Kuan Cheng, William Hoza#### Hitting Sets Give Two-Sided Derandomization of Small Space

Revisions: 1

__
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

William Hoza

We study hardness amplification in the context of two well-known "moderate" average-case hardness results for $\mathrm{AC}^0$ circuits. First, we investigate the extent to which $\mathrm{AC}^0$ circuits of depth $d$ can approximate $\mathrm{AC}^0$ circuits of some larger depth $d + k$. The case $k = 1$ is resolved by HÃ¥stad, Rossman, ... more >>>

Lijie Chen, William Hoza, Xin Lyu, Avishay Tal, Hongxun Wu

A weighted pseudorandom generator (WPRG) is a generalization of a pseudorandom generator (PRG) in which, roughly speaking, probabilities are replaced with weights that are permitted to be positive or negative. We present new explicit constructions of WPRGs that fool certain classes of standard-order read-once branching programs. In particular, our WPRGs ... more >>>

Pooya Hatami, William Hoza

This is a survey of unconditional *pseudorandom generators* (PRGs). A PRG uses a short, truly random seed to generate a long, "pseudorandom" sequence of bits. To be more specific, for each restricted model of computation (e.g., bounded-depth circuits or read-once branching programs), we would like to design a PRG that ... more >>>

William Hoza

Is randomness ever necessary for space-efficient computation? It is commonly conjectured that L = BPL, meaning that halting decision algorithms can always be derandomized without increasing their space complexity by more than a constant factor. In the past few years (say, from 2017 to 2022), there has been some exciting ... more >>>

Pooya Hatami, William Hoza, Avishay Tal, Roei Tell

For $n \in \mathbb{N}$ and $d = o(\log \log n)$, we prove that there is a Boolean function $F$ on $n$ bits and a value $\gamma = 2^{-\Theta(d)}$ such that $F$ can be computed by a uniform depth-$(d + 1)$ $\text{AC}^0$ circuit with $O(n)$ wires, but $F$ cannot be computed ... more >>>

William Hoza

Three decades ago, Nisan constructed an explicit pseudorandom generator (PRG) that fools width-$n$ length-$n$ read-once branching programs (ROBPs) with error $\varepsilon$ and seed length $O(\log^2 n + \log n \cdot \log(1/\varepsilon))$ (Combinatorica 1992). Nisan's generator remains the best explicit PRG known for this important model of computation. However, a recent ... more >>>

Pooya Hatami, William Hoza, Avishay Tal, Roei Tell

We present new constructions of pseudorandom generators (PRGs) for two of the most widely-studied non-uniform circuit classes in complexity theory. Our main result is a construction of the first non-trivial PRG for linear threshold (LTF) circuits of arbitrary constant depth and super-linear size. This PRG fools circuits with depth $d\in\mathbb{N}$ ... more >>>

William Hoza, Edward Pyne, Salil Vadhan

We prove that the Impagliazzo-Nisan-Wigderson (STOC 1994) pseudorandom generator (PRG) fools ordered (read-once) permutation branching programs of unbounded width with a seed length of $\widetilde{O}(\log d + \log n \cdot \log(1/\varepsilon))$, assuming the program has only one accepting vertex in the final layer. Here, $n$ is the length of the ... more >>>

Kuan Cheng, William Hoza

A hitting set is a "one-sided" variant of a pseudorandom generator (PRG), naturally suited to derandomizing algorithms that have one-sided error. We study the problem of using a given hitting set to derandomize algorithms that have two-sided error, focusing on space-bounded algorithms. For our first result, we show that if ... more >>>

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 >>>