activity
20142017
most citedTypically-Correct Derandomization for Small Time and Space

2 citations · 4 across the 4 of their papers we have counts for

collaborators

6 papers

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}}(…

quant-ph2016

Universal Bell Correlations Do Not Exist

Cole A. Graham, William M. Hoza

We prove that there is no finite-alphabet nonlocal box that generates exactly those correlations that can be generated using a maximally entangled pair of qubits. More generally, w…

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…

cs.DS2014

The Adversarial Noise Threshold for Distributed Protocols

William M. Hoza, Leonard J. Schulman

We consider the problem of implementing distributed protocols, despite adversarial channel errors, on synchronous-messaging networks with arbitrary topology. In our first result we…