
William M. Hoza
Catholic theorem wielder

About me:
I'm a grad student at UT Austin studying theoretical
computer science. I'm generally interested in
the extent to
which stuff can be figured out. I'm especially interested
in computational complexity theory. In my view, it's the natural
habitat of:

Some of my favorite mathematical objects, like
randomness extractors,
branching programs,
pseudorandom generators, and
error correcting codes.

Some of my favorite theorems, like the
time hierarchy theorem,
the KarchmerWigderson theorem,
the SaksZhou theorem,
and Bell's theorem.

Some of my favorite open questions, like
P vs. NP,
L vs. RL, and
BPP vs. BQP.
Research papers:

Universal Bell Correlations Do Not Exist.
With Cole A. Graham. Preprint, 2016.
Summary for curious nonexperts:
[show]
Bell's theorem says, roughly, that it follows from the laws
of quantum mechanics that two parties can interact
instantaneously across arbitrary distances. This phenomenon,
called "quantum nonlocality", has been called "the most
profound discovery of science". The nature of these
"interactions" is notoriously subtle. For example, the
nocommunication theorem says that quantum nonlocality is
not useful for sending genuine signals. In this paper, we
rule out one possible approach to characterizing the exact
extent of the "nonlocal powers" granted by the laws of
quantum mechanics. In particular, a "correlation box" is any
hypothetical device that takes an input from each of two
parties and gives an output to each of them. We prove that
quantum nonlocality is not quite equivalent to any
correlation box that has only finitely many possible inputs
and outputs.

Preserving Randomness for Adaptive Algorithms.
With Adam R. Klivans. Preprint, updated 2017.
Summary for curious nonexperts:
[show]
Suppose you have a randomized algorithm that estimates some
numeric quantity, and you want to use it as a subroutine,
i.e. a building block in some other algorithm. Suppose the
estimation algorithm makes n coin tosses, and you
plan to execute it k times. This situation seems
to call for nk coin tosses in total. In this paper,
we show that you can actually get away with only making
about n + k coin tosses if you use some tricks.

Targeted Pseudorandom Generators, Simulation Advice Generators, and Derandomizing Logspace.
With Chris Umans. To appear in STOC 2017.
Summary for curious nonexperts:
[show]
There's a wellknown conjecture in complexity theory
("L = BPL") that says that randomness isn't useful for
solving problems using a small amount of computer memory.
The most promising approach to proving this conjecture is to
design a suitable kind of "pseudorandom generator". But in
principle, one could hope to prove L = BPL using a totally
different approach. In this paper, we prove a theorem that
can be roughly stated as follows. If every true statement
along the lines of L = BPL can be proven using the
pseudorandom generator approach, then in fact L = BPL
(actually the conclusion is slightly weaker).

The Adversarial Noise Threshold for Distributed Protocols.
With Leonard J. Schulman. In SODA 2016, pages 240  258.
Summary for curious nonexperts:
[show]
Imagine that many people (or computers) are connected by a
network of communication channels. They would like to have a
conversation, but unfortunately, an adversary is altering
their messages to confuse them. The parties may deal with
this noise by encoding their conversation in whatever way
they like. In this paper, we determine the maximum amount of
noise that can be tolerated in a couple different models as
a function of the particular communication network.
Political opinions:
Just in case you read my philosophical opinions and you're
still looking for something to disagree with me about :)

I support a ban on abortion. I support promother
legislation, including governmentfunded pregnancy centers
and legally mandated paid maternity leave.

I support repealing the second amendment. In the meantime,
I support strict gun control laws that do not violate the
second amendment.

I support a ban on physicianassisted suicide and other
forms of euthanasia.

I support extensive government regulations and programs
designed to protect the environment.

I support a ban on any stem cell research that involves
intentionally destroying human embryos.

I support a ban on capital punishment.

I oppose civil samesex "marriage" constructs. I recognize
that having homosexual inclinations does not mean that you've
done anything wrong. I support legislation that protects the
LGBT community from unjust discrimination and harrassment. I
try to be a good ally.

I oppose torture. More generally, I oppose almost all
violent actions performed by the U.S. military.

I support originalism.

I support making it sufficiently easy to legally immigrate
to the U.S. that there is essentially no temptation to
immigrate here illegally.

I support a ban on human cloning.

I support expanded welfare programs.

I oppose efforts by the NSA to weaken cryptographic
software.
Video games, etc.:
I occasionally masquerade as a programmer, in order to provide you with ways to waste your time:
Contact:
whoza@utexas.edu
As for wisdom, where does she come from?
Where is the place of understanding?
She is hidden from the eyes of every living thing;
even from the birds of the air she is concealed.
(Job 28:2021)