Back to my homepage


Research

I study computational complexity theory. I'm especially interested in pseudorandom generators and the derandomization of space-bounded computation. I also like circuit complexity. Click here to see a poster-style image from February 2024 summarizing my research areas.

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. Fooling Near-Maximal Decision Trees

    William M. Hoza

    Manuscript 2025

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

  3. Implications of Better PRGs for Permutation Branching Programs

    Dean Doron and William M. Hoza

    Manuscript 2024

  4. Limitations of the Impagliazzo-Nisan-Wigderson Pseudorandom Generator Against Permutation Branching Programs

    William M. Hoza, Edward Pyne, and Salil Vadhan

    Algorithmica 2024

  5. A Technique for Hardness Amplification Against $\mathsf{AC}^0$

    William M. Hoza

    CCC 2024

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

  7. Depth-$d$ Threshold Circuits vs. Depth-$(d + 1)$ AND-OR Trees

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

    STOC 2023

  8. Hitting Sets for Regular Branching Programs

    Andrej Bogdanov, William M. Hoza, Gautam Prakriya, and Edward Pyne

    CCC 2022

  9. Better Pseudodistributions and Derandomization for Space-Bounded Computation

    William M. Hoza

    RANDOM 2021 • ToC (special issue for RANDOM 2021, to appear)

  10. Fooling Constant-Depth Threshold Circuits

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

    FOCS 2021

  11. Pseudorandom Generators for Unbounded-Width Permutation Branching Programs

    William M. Hoza, Edward Pyne, and Salil Vadhan

    ITCS 2021

  12. Hitting Sets Give Two-Sided Derandomization of Small Space

    Kuan Cheng and William M. Hoza

    CCC 2020 • ToC 2022 (special issue for CCC 2020)

  13. Log-Seed Pseudorandom Generators via Iterated Restrictions

    Dean Doron, Pooya Hatami, and William M. Hoza

    CCC 2020

  14. Near-Optimal Pseudorandom Generators for Constant-Depth Read-Once Formulas

    Dean Doron, Pooya Hatami, and William M. Hoza

    CCC 2019

  15. Simple Optimal Hitting Sets for Small-Success RL

    William M. Hoza and David Zuckerman

    FOCS 2018 • SICOMP 2020

  16. Typically-Correct Derandomization for Small Time and Space

    William M. Hoza

    CCC 2019

  17. Quantum Communication-Query Tradeoffs

    William M. Hoza

    Manuscript 2017

  18. Universal Bell Correlations Do Not Exist

    Cole A. Graham and William M. Hoza

    PRL 2017

  19. Preserving Randomness for Adaptive Algorithms

    William M. Hoza and Adam R. Klivans

    RANDOM 2018

  20. Targeted Pseudorandom Generators, Simulation Advice Generators, and Derandomizing Logspace

    William M. Hoza and Chris Umans

    STOC 2017 • SICOMP 2022 (special section for STOC 2017)

  21. 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).