William M. Hoza
About me:
I'm a fourthyear grad student at UT Austin studying
theoretical
computer science. I have the good fortune to be advised by
David Zuckerman. Previously, I was an undergrad at Caltech, where I was lucky to receive valuable mentorship from
Leonard Schulman and
Chris Umans.
I study computational complexity theory, which means I'm interested in the strengths of different computational resources. To what extent does randomness provide a computational advantage? How about quantum mechanics? Does parallelism always give a huge speedup? Is space more useful than time? Is it ever easier to check your work than it is to solve a problem from scratch? All of these questions can be made mathematically precise, and nobody knows the answers.
My personal favorite open question is the "
L vs.
BPL" question: Is randomness ever necessary to solve a problem using only a little memory? To work on resolving this question, people like me study "pseudorandomness", which is any phenomenon where something looks more random than it actually is.
Research papers: (Expand for more info)
LogSeed Pseudorandom Generators via Iterated Restrictions
With Dean Doron and Pooya Hatami. Manuscript, 2019.
Notsoabstract: A "pseudorandom generator" is an algorithm that makes a few coin tosses and outputs a long sequence of bits (x
_{1}, x
_{2}, x
_{3}, ...) that "look random" in some sense. In this paper, we present a pseudorandom generator whose output looks random in the following sense. Consider a polynomial such as
y = x_{1}x_{3} + x_{2}x_{7}x_{8} + x_{4}x_{5} + ...
Each variable is only allowed to appear one time (it's "readonce"). The arithmetic is mod 2 (+ is really XOR, and y is either 0 or 1). For every polynomial y of that form, the expected value of y when you plug in the output of our pseudorandom generator is approximately the same (say, to within plus or minus 0.01) as it is when you plug in truly random bits. For a fixed error value like 0.01, our pseudorandom generator is *optimal*, i.e., it makes essentially the smallest possible number of coin tosses.
NearOptimal Pseudorandom Generators for ConstantDepth ReadOnce Formulas
With Dean Doron and Pooya Hatami. In CCC 2019.
Notsoabstract: A "pseudorandom generator" is an algorithm that makes a few coin tosses and outputs a long sequence of bits (x
_{1}, x
_{2}, x
_{3}, ...) that "look random" in some sense. In this paper, we present a pseudorandom generator whose output looks random in the following sense. Consider a statement that says something like
((x_{3} = 0 AND x_{7} = 1 AND x_{2} = 1) OR (x_{6} = 1 AND (x_{5} = 0 OR x_{1} = 0) AND ...)).
Each variable is only allowed to appear one time, and the parentheses are only allowed to be nested to a depth of, say, 100. For every statement of that form, the probability that the statement evaluates to true when you plug in the output of our pseudorandom generator is roughly the same as the probability that the statement evaluates to true when you plug in truly random bits. Our pseudorandom generator is "nearoptimal", i.e., our algorithm makes very few coin tosses.
Versions: The
CCC proceedings version has some minor presentational improvements compared to the
ECCC version.
Presentation materials available online:

[video]
[slides]  from
my presentation at BIRS workshop 19w5088 (July 2019). I used very similar slides for my presentation for my "Research Preparation Exam" (May 2019), part of the UT CS PhD program.

[slides]  from my presentation at CCC (July 2019).
Simple Optimal Hitting Sets for SmallSuccess RL
With David Zuckerman. In FOCS 2018.
Notsoabstract: A "decision algorithm" takes as
input a string and either "accepts" or "rejects" the
string. A "hitting set" is a set of strings so that if A
is an efficient decision algorithm that accepts a decent
fraction of inputs, then A accepts some string in the
hitting set. For this paper, "efficient" means that A uses
only a small amount of memory and reads its input just
once from left to right. In this paper, we present a new
hitting set. Our hitting set is smaller than any hitting set
discovered previously.
Versions: The
FOCS proceedings version has a couple extra references and different formatting compared to the
ECCC version.
Presentation materials available online:

[slides]  from my presentation at FOCS (October 2018).

[slides]  from my presentation at Dagstuhl Seminar 18391 (September 2018). I used very similar slides for my presentation at China Theory Week (September 2018) and my presentation at the UT Austin CS Theory Seminar (February 2019).

[video]  from David's presentation at Princeton Theory Lunch (October 2018).
Notes: The main result of the paper is covered in
these lecture notes for a course taught by Amnon TaShma. The paper is discussed in
this talk by Omer Reingold. The paper is mentioned in
this post on Lance Fortnow and Bill Gasarch's blog.
TypicallyCorrect Derandomization for Small Time and Space
In CCC 2019.
Notsoabstract: A "randomized" algorithm tosses
coins to make decisions, whereas a "deterministic"
algorithm doesn't use any randomness. Most theoretical
computer scientists believe that if a problem can be
solved by a randomized algorithm, then it can also be
solved by a deterministic algorithm that uses about the
same amount of time and memory. But nobody knows how to
prove it. In this paper, we prove that if a problem can
be solved by a fast randomized algorithm, then it can
also be solved by a deterministic algorithm that uses
about the same amount of memory, with the caveat that
the deterministic algorithm might give the wrong answer
on a tiny fraction of inputs.
Versions: The
arXiv version and the
CCC proceedings version are the same except for formatting.
Presentation materials available online:

[video]
[slides]  from my presentation at CCC (July 2019)

[slides]  from my presentation at HUJI's Theory of Computer Science Seminar (March 2018). I used very similar slides for my presentations at Weizmann Institute's Foundations of Computer Science Seminar (March 2018) and TAU's Theory of Computation Seminar (March 2018).
Quantum CommunicationQuery Tradeoffs
Manuscript, 2017.
Notsoabstract:
Quantum algorithms are algorithms that exploit quantum
effects, requiring special hardware that, broadly
speaking, nobody has managed to build yet. In this
paper, we study quantum algorithms for two types of
problems. In the first type of problem, Alice has some
data x, Bob has some data y, and the two of them would
like to figure out whether the pair (x, y) has some
property P using as little communication as possible.
For example, maybe x and y are numbers between 1 and a
million, and P is the property that x > y. The second
type of problem is similar to the game 20 Questions.
Alice chooses x. If Bob specifies y, then Alice tells
him whether (x, y) has property P. Bob's goal is to
learn x by making as few queries as possible. We prove
that if the same property P is used to formulate each
problem, then the two problems can't both have extremely
efficient quantum algorithms.
Universal Bell Correlations Do Not Exist
With Cole A. Graham. In PRL, 2017.
Notsoabstract:
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, aside from quantum
nonlocality, another situation in which two parties can
interact in a limited way is if there is some discrete,
classical device that each party is able to interact with.
We prove that quantum nonlocality is not quite equivalent to
any such discrete, classical device.
Versions: The
PRL version,
also available
on this site,
is much more compact than the earlier
arXiv version.
The arXiv version has essentially the same results, but it
has more detailed definitions and proofs and some suggested
open problems. The arXiv version also uses slightly
different notation and is missing some references.
Presentation materials available online:

[slides]  from my presentation in Scott Aaronson's course "Topics in Quantum and Classical Complexity Theory" (December 2016)
Copyright information:
© 2017 American Physical Society.
Preserving Randomness for Adaptive Algorithms
With Adam R. Klivans. In RANDOM 2018.
Notsoabstract:
Suppose you have a randomized algorithm that estimates
some numeric quantity, and you plan to use it
k
times. Suppose the estimation algorithm makes
n
coin tosses. 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.
Versions:
The
arXiv version
and the
ECCC version
are identical. The
RANDOM proceedings version is more compact and skips a lot of the material.
Presentation materials available online:

[video]  from Adam's presentation at the Simons Institute "Proving and Using Pseudorandomness" workshop (March 2017)

[slides]  from my presentation at Caltech's CS Theory Seminar (May 2017)

[slides]  from my presentation at RANDOM (August 2018)
Targeted Pseudorandom Generators, Simulation Advice Generators, and Derandomizing Logspace
With Chris Umans. In STOC 2017.
Erratum (May 2017): In Lemma 2, the
space complexity should be O(s + log w + log(1/δ)
+ log(1/γ)). That is, there is a missing O(log(1/δ))
term in the lemma statement. This does not
affect anything else in the paper.
Notsoabstract:
There's a wellknown conjecture in complexity theory
("L = BPL") that says that randomness isn't necessary 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).
Versions:
The
STOC proceedings version
and the
arXiv version are the same except for formatting.
Presentation materials available online:
Notes: This paper was invited to the SIAM Journal
of Computing special issue for STOC 2017. This paper is mentioned in
this post
by Oded Goldreich.
The Adversarial Noise Threshold for Distributed Protocols
With Leonard J. Schulman. In SODA 2016.
Notsoabstract:
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.
Versions:
I recommend that you read the
SODA proceedings version.
The SODA reviewers' feedback never got incorporated into the
arXiv version.
Presentation materials available online:

[slides]  from my presentation at SODA (January 2016)

[poster]  from my presentation at Caltech's CMS "Celebration of Undergraduate Research" (May 2015)
Notes: This paper is summarized in Section
7.3 of
this survey article
by Ran Gelles.
Other stuff you can read: (Expand for more info)
A ThreePlayer Pictionary Variant
With Paige Kubenka and Alicia Torres. Unpublished, 2018.
Description: This is an article in which we describe a
threeplayer game similar to Pictionary. Our game has no teams.
What's My ProLife Line?
With Alicia Torres. Ongoing, started 2018.
Top 10 Blatant Contradictions in Math
Unpublished, 2016.
Description: This is a satirical listicle.
101 Illustrated Real Analysis Bedtime Stories
With Laura Shou and others. Unfinished, last updated 2016.
Description: This is a recreational book. We present
real analysis in a way that is supposed to be enjoyable to
read.
A "Can" of Worms
Unpublished, 2016.
Description: This is an essay I wrote as an undergrad
for a class on free will taught by
Christopher Hitchcock.
In the essay, I respond to a specific objection to
compatibilism,
the thesis that free will is possible even in a deterministic
universe.
Notes: This essay won the Gordon McClure Memorial
Communication Prize in Philosophy from Caltech's HSS division.
Philosophical opinions
Political opinions (just in case you read my
philosophical opinions and you're still looking for something
to disagree with me about 🙂)

I favor making it very easy to legally immigrate to the U.S.
I want the border between the U.S. and Mexico to be similar to
the border between Texas and New Mexico. I don't think any
special excuse or reason should be required to become a U.S.
citizen.

I support a ban on any stem cell research that involves
intentionally destroying human embryos. I also support bans
on in vitro fertilization and human cloning. I think
we all have fundamental dignity and value that doesn't
depend on the circumstances of our conception, and I respect
persons conceived through in vitro fertilization as
equals.

I favor 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 abortion. I think we should use nonviolent
methods to support pregnant women. I support
governmentfunded pregnancy centers, and I think the
government should ensure that all employed new mothers have
access to paid maternity leave.

I favor giving every citizen the right to vote,
regardless of age or criminal history. Yes, I'm serious,
regardless of age.

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

I oppose torture. More generally, I oppose almost all violent
actions performed by the U.S. military. I am grateful for the
service of those members of the military who honorably and
ethically defend the country.

I oppose civil samesex marriage institutions. I recognize
that there is nothing shameful about being gay or lesbian
or bisexual. I think sexual minorities are among those most
harmed by samesex marriage. I support legislation that
protects sexual minorities from unjust discrimination and
harrassment.

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

I support originalism.

I favor abolishing capital punishment.

I support serious free speech protections at public
universities.

I support extensive welfare programs.

I oppose efforts by the NSA to weaken cryptographic
software.
I'd be happy to chat about any of this stuff in person.
Video games, etc.:
I occasionally masquerade as a programmer, in order to provide you with ways to waste your time:
Contact:
whoza@utexas.edu
"Finally, brothers, whatever is true, whatever is honorable, whatever is just, whatever is pure, whatever is lovely, whatever is gracious, if there is any excellence and if there is anything worthy of praise, think about these things." (Philippians 4:8)