William M. Hoza

29 papers A* 5A 10Journal 12Unranked 2

Year	Rank	Type	Title / Venue / Authors
2025	A	`conf`	Fooling Near-Maximal Decision Trees. APPROX/RANDOM William M. Hoza, Zelin Lv
2025	A	`conf`	Implications of Better PRGs for Permutation Branching Programs. APPROX/RANDOM Dean Doron, William M. Hoza
2025	A	`conf`	On Sums of INW Pseudorandom Generators. APPROX/RANDOM William M. Hoza, Zelin Lv
2024	A	`conf`	A Technique for Hardness Amplification Against AC⁰. CCC William M. Hoza
2024	J	`jnl`	Limitations of the Impagliazzo-Nisan-Wigderson Pseudorandom Generator Against Permutation Branching Programs. Algorithmica William M. Hoza, Edward Pyne, Salil P. Vadhan
2024	J	`jnl`	Provable Tempered Overfitting of Minimal Nets and Typical Nets. CoRR Itamar Harel, William M. Hoza, Gal Vardi, Itay Evron, Nathan Srebro, Daniel Soudry
2023	A*	`conf`	Depth-d Threshold Circuits vs. Depth-(d+1) AND-OR Trees. STOC Pooya Hatami, William M. Hoza, Avishay Tal, Roei Tell
2023	A*	`conf`	Weighted Pseudorandom Generators via Inverse Analysis of Random Walks and Shortcutting. FOCS Lijie Chen, William M. Hoza, Xin Lyu, Avishay Tal, Hongxun Wu
2022	J	`jnl`	Hitting Sets Give Two-Sided Derandomization of Small Space. Theory Comput. Kuan Cheng, William M. Hoza
2022	A	`conf`	Hitting Sets for Regular Branching Programs. CCC Andrej Bogdanov, William M. Hoza, Gautam Prakriya, Edward Pyne
2022	J	`jnl`	Recent Progress on Derandomizing Space-Bounded Computation. Bull. EATCS William M. Hoza
2022	J	`jnl`	Targeted Pseudorandom Generators, Simulation Advice Generators, and Derandomizing Logspace. SIAM J. Comput. William M. Hoza, Chris Umans
2021	—	`conf`	Better Pseudodistributions and Derandomization for Space-Bounded Computation. APPROX-RANDOM William M. Hoza
2021	A*	`conf`	Fooling Constant-Depth Threshold Circuits (Extended Abstract). FOCS Pooya Hatami, William M. Hoza, Avishay Tal, Roei Tell
2021	A	`conf`	Pseudorandom Generators for Unbounded-Width Permutation Branching Programs. ITCS William M. Hoza, Edward Pyne, Salil P. Vadhan
2020	A	`conf`	Hitting Sets Give Two-Sided Derandomization of Small Space. CCC Kuan Cheng, William M. Hoza
2020	A	`conf`	Log-Seed Pseudorandom Generators via Iterated Restrictions. CCC Dean Doron, Pooya Hatami, William M. Hoza
2020	J	`jnl`	Simple Optimal Hitting Sets for Small-Success RL. SIAM J. Comput. William M. Hoza, David Zuckerman
2019	A	`conf`	Near-Optimal Pseudorandom Generators for Constant-Depth Read-Once Formulas. CCC Dean Doron, Pooya Hatami, William M. Hoza
2019	A	`conf`	Typically-Correct Derandomization for Small Time and Space. CCC William M. Hoza
2018	—	`conf`	Preserving Randomness for Adaptive Algorithms. APPROX-RANDOM William M. Hoza, Adam R. Klivans
2017	J	`jnl`	Quantum Communication-Query Tradeoffs. CoRR William M. Hoza
2017	A*	`conf`	Targeted pseudorandom generators, simulation advice generators, and derandomizing logspace. STOC William M. Hoza, Chris Umans
2017	J	`jnl`	Typically-Correct Derandomization for Small Time and Space. CoRR William M. Hoza
2016	J	`jnl`	Preserving Randomness for Adaptive Algorithms. CoRR William M. Hoza, Adam R. Klivans
2016	J	`jnl`	Preserving Randomness for Adaptive Algorithms. Electron. Colloquium Comput. Complex. William M. Hoza, Adam R. Klivans
2016	J	`jnl`	Targeted Pseudorandom Generators, Simulation Advice Generators, and Derandomizing Logspace. CoRR William M. Hoza, Chris Umans
2016	A*	`conf`	The Adversarial Noise Threshold for Distributed Protocols. SODA William M. Hoza, Leonard J. Schulman
2014	J	`jnl`	The Adversarial Noise Threshold for Distributed Protocols. CoRR William M. Hoza, Leonard J. Schulman