William M. Hoza

most citedTypically-Correct Derandomization for Small Time and Space

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

collaborators

5 papers

cs.CC2017★ 2 cited

Typically-Correct Derandomization for Small Time and Space

William M. Hoza

Suppose a language $L$ can be decided by a bounded-error randomized algorithm that runs in space $S$ and time $n \cdot poly (S)$ . We give a randomized algorithm for $L$ that…

cs.CC2017★ 2 cited

Quantum Communication-Query Tradeoffs

William M. Hoza

For any function $f : X \times Y \to Z$ , we prove that $Q^{* cc} (f) \cdot Q^{OIP} (f) \cdot (lo g Q^{OIP} (f) + lo g ∣ Z ∣) \geq Ω (lo g ∣ X ∣)$ . 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 $Est$ is a randomized estimation algorithm that uses $n$ random bits and outputs values in $R^{d}$ . We show how to execute $Est$ on $k$ 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…