# Theoretical computer science stuff

I'm currently a postdoc "at" the Simons Institute for the Theory of Computing. I put "at" in quotes because I still physically live in Austin, TX for now, where I recently completed my grad school work (my official graduation date is in August 2021).

I study *pseudorandomness and derandomization*. More generally, I'm interested in computational complexity theory and the analysis of Boolean functions.

## A short explanation of what "derandomization" means (for curious outsiders)

Some algorithms use randomness to solve computational problems. For example, one of the best known methods for finding a large prime number is to pick a large number at random, check if it's prime, and try again if necessary.

You can think of randomness as a scarce computational resource — a type of algorithmic "fuel." Randomized algorithms are okay, but all else being equal, an algorithm that uses *fewer* random bits is better than an algorithm that uses more random bits, just like a faster algorithm is better than a slower algorithm, or a car that uses less gasoline is better than a car that uses more gasoline. Algorithms that don't use any randomness ("deterministic" algorithms) are best of all. For example, it would be nice to have a fast deterministic algorithm for finding large prime numbers. "Derandomization" is the art of converting randomized algorithms into deterministic algorithms.

One approach for using fewer random bits is to design *pseudorandom generators*, which use a small number of random bits to generate a long sequence of bits that "look random" and can often be used as a substitute for truly random bits. I'm especially interested in pseudorandom generators that are *provably* correct.

I'm grateful for all the mentorship I've received, especially from David Zuckerman (my graduate advisor) and Leonard Schulman and Chris Umans (undergraduate research mentors).

My research papers are listed below, sorted by the date they were first posted online (newest to oldest). If you have a question or comment, send me an email! Like most researchers, I like getting emails about my work.

- Better Pseudodistributions and Derandomization for Space-Bounded Computation

William M. Hoza

RANDOM 2021 (to appear) - Fooling Constant-Depth Threshold Circuits

Pooya Hatami, William M. Hoza, Avishay Tal, and Roei Tell

Manuscript 2021 - Pseudorandom Generators for Unbounded-Width Permutation Branching Programs

William M. Hoza, Edward Pyne, and Salil Vadhan

ITCS 2021 - Hitting Sets Give Two-Sided Derandomization of Small Space

Kuan Cheng and William M. Hoza

CCC 2020 - Log-Seed Pseudorandom Generators via Iterated Restrictions

Dean Doron, Pooya Hatami, and William M. Hoza

CCC 2020 - Near-Optimal Pseudorandom Generators for Constant-Depth Read-Once Formulas

Dean Doron, Pooya Hatami, and William M. Hoza

CCC 2019 - Simple Optimal Hitting Sets for Small-Success RL

William M. Hoza and David Zuckerman

FOCS 2018 • SICOMP 2020 - Typically-Correct Derandomization for Small Time and Space

William M. Hoza

CCC 2019 - Quantum Communication-Query Tradeoffs

William M. Hoza

Manuscript 2017 - Universal Bell Correlations Do Not Exist

Cole A. Graham and William M. Hoza

PRL 2017 - Preserving Randomness for Adaptive Algorithms

William M. Hoza and Adam R. Klivans

RANDOM 2018 - Targeted Pseudorandom Generators, Simulation Advice Generators, and Derandomizing Logspace

William M. Hoza and Chris Umans

STOC 2017 • SICOMP 2021 (special issue for STOC 2017) - The Adversarial Noise Threshold for Distributed Protocols

William M. Hoza and Leonard Schulman

SODA 2016