Research
I'm a member of the UChicago CS Theory Group. I study computational complexity theory. My research papers are listed below. If you have a question or comment about my work, please send me an email!
I am experimenting with sharing raw AI-generated proofs, in addition to traditional research papers. See this page.
AI-era papers (i.e., these papers describe AI-assisted research)
- Multi-Access Randomness Saves Space, Even for Halting Algorithms
William M. Hoza
Manuscript 2026
- The BRRY Analysis of the INW Pseudorandom Generator is Optimal
William M. Hoza and Yakov Shalunov
Manuscript 2026
- Deterministic, Oblivious Isolation for Space-Bounded Computation Requires Large Weights
William M. Hoza
Manuscript 2026
Pre-AI papers (i.e., these papers describe research done without significant AI assistance)
- On Sums of INW Pseudorandom Generators
William M. Hoza and Zelin Lv
RANDOM 2025
- Fooling Near-Maximal Decision Trees
William M. Hoza and Zelin Lv
RANDOM 2025
- Provable Tempered Overfitting of Minimal Nets and Typical Nets
Itamar Harel, William M. Hoza, Gal Vardi, Itay Evron, Nathan Srebro, and Daniel Soudry [non-alphabetical]
NeurIPS 2024
- Implications of Better PRGs for Permutation Branching Programs
Dean Doron and William M. Hoza
RANDOM 2025
- Limitations of the Impagliazzo-Nisan-Wigderson Pseudorandom Generator Against Permutation Branching Programs
William M. Hoza, Edward Pyne, and Salil Vadhan
Algorithmica 2024
- A Technique for Hardness Amplification Against $\mathsf{AC}^0$
William M. Hoza
CCC 2024 • computational complexity 2026 (special issue for CCC 2024)
- 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
- Paradigms for Unconditional Pseudorandom Generators (survey)
Pooya Hatami and William M. Hoza
FnT TCS 2024
- Recent Progress on Derandomizing Space-Bounded Computation (survey)
William M. Hoza
BEATCS 2022
- Depth-$d$ Threshold Circuits vs. Depth-$(d + 1)$ AND-OR Trees
Pooya Hatami, William M. Hoza, Avishay Tal, and Roei Tell
STOC 2023
- Hitting Sets for Regular Branching Programs
Andrej Bogdanov, William M. Hoza, Gautam Prakriya, and Edward Pyne
CCC 2022
- Better Pseudodistributions and Derandomization for Space-Bounded Computation
William M. Hoza
RANDOM 2021 • ToC (special issue for RANDOM 2021, to appear)
- Fooling Constant-Depth Threshold Circuits
Pooya Hatami, William M. Hoza, Avishay Tal, and Roei Tell
FOCS 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 • ToC 2022 (special issue for 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 2022 (special section for STOC 2017)
- The Adversarial Noise Threshold for Distributed Protocols
William M. Hoza and Leonard Schulman
SODA 2016