William M. Hoza
Catholic theorem wielder
About me: I'm a grad student at UT Austin studying theoretical computer science. I'm interested in the power of different computational resources. Is randomness useful for computation? How about quantum mechanics? Does parallelism always give a huge computational advantage? 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 problem is the "L vs. BPL" problem: Is randomness ever helpful for solving a problem using as little memory as possible?
Research papers:
  • Typically-Correct Derandomization for Small Time and Space.
    Preprint, 2017. More info: [show]
    Not-so-abstract: 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.
  • Quantum Communication-Query Tradeoffs.
    Preprint, 2017. More info: [show]
    Not-so-abstract: 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 119, 050402 (2017). More info: [show]
    Not-so-abstract: 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 no-communication 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.

    Study resources: I presented this paper in Scott Aaronson's course "Topics in Quantum and Classical Complexity Theory" in Fall 2016; the slides are available here.

    Copyright information: © 2017 American Physical Society.
  • Preserving Randomness for Adaptive Algorithms.
    With Adam R. Klivans. Preprint, updated 2017. More info: [show]
    Not-so-abstract: 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.

    Study resources: Adam Klivans presented this paper at the Simons Institute "Proving and Using Pseudorandomness" workshop in March 2017; a video is available here. I presented this paper at Caltech's CS Theory Seminar in May 2017; the slides are available here.
  • Targeted Pseudorandom Generators, Simulation Advice Generators, and Derandomizing Logspace.
    With Chris Umans. In STOC 2017, pages 629 - 640. More info, including erratum: [show]
    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.

    Not-so-abstract: There's a well-known 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).

    Versions: The STOC proceedings version and the arXiv version are the same except for formatting.

    Study resources: I presented this paper at Dagstuhl Seminar 16411; the slides are available here. I presented this paper at STOC 2017; the slides are available here, the poster is available here, and a video of the presentation is available here.

    Notes: This paper was invited to the SIAM Journal of Computing special issue for STOC 2017. Oded Goldreich has commented on this paper.
  • The Adversarial Noise Threshold for Distributed Protocols.
    With Leonard J. Schulman. In SODA 2016, pages 240 - 258. More info: [show]
    Not-so-abstract: 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.

    Study resources: This paper is summarized in Section 7.3 of this survey article by Ran Gelles. I presented this paper at SODA 2016; the slides are available here. I presented this paper at Caltech's 2015 CMS "Celebration of Undergraduate Research"; the poster is available here.
Other stuff you can read:
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 support a ban on abortion. I support pro-mother legislation, including government-funded 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 physician-assisted suicide and all 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 same-sex "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 am grateful for the service of those members of the military who honorably and ethically defend the country.
  • 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:20-21)