Back to my homepage

# Research

I study computational complexity theory. I'm especially interested in pseudorandomness, derandomization, and circuit complexity. Click here to see a poster-style image from February 2024 summarizing my research areas.

Click here for a short explanation of what "derandomization" means (for curious outsiders).

Some algorithms use randomness to solve computational problems. For example, one of the best methods known 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.

My research papers are listed below. If you have a question or comment, please send me an email! Like most researchers, I like getting emails about my work.

## Surveys

1. Paradigms for Unconditional Pseudorandom Generators
Pooya Hatami and William M. Hoza
FnT TCS 2024
2. Recent Progress on Derandomizing Space-Bounded Computation
William M. Hoza
BEATCS 2022

## Ordinary research papers

1. A Technique for Hardness Amplification Against \$\mathsf{AC}^0\$
William M. Hoza
CCC 2024 (to appear)
2. Weighted Pseudorandom Generators via Inverse Analysis of Random Walks and Shortcutting
Lijie Chen, William M. Hoza, Xin Lyu, Avishay Tal, and Hongxun Wu
FOCS 2023
3. Depth-\$d\$ Threshold Circuits vs. Depth-\$(d + 1)\$ AND-OR Trees
Pooya Hatami, William M. Hoza, Avishay Tal, and Roei Tell
STOC 2023
4. Hitting Sets for Regular Branching Programs
Andrej Bogdanov, William M. Hoza, Gautam Prakriya, and Edward Pyne
CCC 2022
5. Better Pseudodistributions and Derandomization for Space-Bounded Computation
William M. Hoza
RANDOM 2021 • ToC (special issue for RANDOM 2021, to appear)
6. Fooling Constant-Depth Threshold Circuits
Pooya Hatami, William M. Hoza, Avishay Tal, and Roei Tell
FOCS 2021
7. Pseudorandom Generators for Unbounded-Width Permutation Branching Programs
William M. Hoza, Edward Pyne, and Salil Vadhan
ITCS 2021
8. Hitting Sets Give Two-Sided Derandomization of Small Space
Kuan Cheng and William M. Hoza
CCC 2020 • ToC 2022 (special issue for CCC 2020)
9. Log-Seed Pseudorandom Generators via Iterated Restrictions
Dean Doron, Pooya Hatami, and William M. Hoza
CCC 2020
10. Near-Optimal Pseudorandom Generators for Constant-Depth Read-Once Formulas
Dean Doron, Pooya Hatami, and William M. Hoza
CCC 2019
11. Simple Optimal Hitting Sets for Small-Success RL
William M. Hoza and David Zuckerman
FOCS 2018 • SICOMP 2020
12. Typically-Correct Derandomization for Small Time and Space
William M. Hoza
CCC 2019
William M. Hoza
Manuscript 2017
14. Universal Bell Correlations Do Not Exist
Cole A. Graham and William M. Hoza
PRL 2017
15. Preserving Randomness for Adaptive Algorithms
William M. Hoza and Adam R. Klivans
RANDOM 2018
16. Targeted Pseudorandom Generators, Simulation Advice Generators, and Derandomizing Logspace
William M. Hoza and Chris Umans
STOC 2017 • SICOMP 2022 (special section for STOC 2017)
17. The Adversarial Noise Threshold for Distributed Protocols
William M. Hoza and Leonard Schulman
SODA 2016

## Dissertation:

Derandomizing Space-Bounded Computation via Pseudorandom Generators and their Generalizations

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