Back to my homepage

Theoretical computer science stuff

I'm currently a fifth-year grad student in the CS department at UT Austin. I have the good fortune to be advised by David Zuckerman. Previously, I was an undergrad at Caltech, where I was lucky to receive valuable mentorship from Leonard Schulman and Chris Umans.

I study pseudorandomness and derandomization. You can think of randomness as a scarce computational resource — a type of algorithmic "fuel." Randomized algorithms are great, but all else being equal, an algorithm that uses fewer random bits is better than an algorithm that uses more random bits. (Analogously, a faster algorithm is better than a slower algorithm; a car that uses less gasoline is better than a car that uses more gasoline.) Deterministic algorithms are best of all. 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.

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

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! I like getting emails about my work (as do most researchers).

  1. Better Pseudodistributions and Derandomization for Space-Bounded Computation
    William M. Hoza
    Manuscript 2021
  2. Fooling Constant-Depth Threshold Circuits
    Pooya Hatami, William M. Hoza, Avishay Tal, and Roei Tell
    Manuscript 2021
  3. Pseudorandom Generators for Unbounded-Width Permutation Branching Programs
    William M. Hoza, Edward Pyne, and Salil Vadhan
    ITCS 2021
  4. Hitting Sets Give Two-Sided Derandomization of Small Space
    Kuan Cheng and William M. Hoza
    CCC 2020
  5. Log-Seed Pseudorandom Generators via Iterated Restrictions
    Dean Doron, Pooya Hatami, and William M. Hoza
    CCC 2020
  6. Near-Optimal Pseudorandom Generators for Constant-Depth Read-Once Formulas
    Dean Doron, Pooya Hatami, and William M. Hoza
    CCC 2019
  7. Simple Optimal Hitting Sets for Small-Success RL
    William M. Hoza and David Zuckerman
    FOCS 2018SICOMP 2020
  8. Typically-Correct Derandomization for Small Time and Space
    William M. Hoza
    CCC 2019
  9. Quantum Communication-Query Tradeoffs
    William M. Hoza
    Manuscript 2017
  10. Universal Bell Correlations Do Not Exist
    Cole A. Graham and William M. Hoza
    PRL 2017
  11. Preserving Randomness for Adaptive Algorithms
    William M. Hoza and Adam R. Klivans
    RANDOM 2018
  12. Targeted Pseudorandom Generators, Simulation Advice Generators, and Derandomizing Logspace
    William M. Hoza and Chris Umans
    STOC 2017SICOMP 2021 (special issue for STOC 2017)
  13. The Adversarial Noise Threshold for Distributed Protocols
    William M. Hoza and Leonard Schulman
    SODA 2016