2 citations · 4 across the 4 of their papers we have counts for
Showing cs.CCShow all
4 papers · 1 filter
cs.CC2017★ 2 cited
Typically-Correct Derandomization for Small Time and Space
William M. Hoza
Suppose a language can be decided by a bounded-error randomized algorithm that runs in space and time . We give a randomized algorithm for that…
cs.CC2017★ 2 cited
Quantum Communication-Query Tradeoffs
William M. Hoza
For any function , we prove that . Here, $Q^{*\text{cc}}(…
cs.CC2016
Preserving Randomness for Adaptive Algorithms
William M. Hoza, Adam R. Klivans
Suppose is a randomized estimation algorithm that uses random bits and outputs values in . We show how to execute on adaptively…
cs.CC2016
Targeted Pseudorandom Generators, Simulation Advice Generators, and Derandomizing Logspace
William M. Hoza, Chris Umans
Assume that for every derandomization result for logspace algorithms, there is a pseudorandom generator strong enough to nearly recover the derandomization by iterating over all se…