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:
Research papers:
  • Universal Bell Correlations Do Not Exist.
    With Cole A. Graham. Preprint, 2016.
    Summary for curious non-experts: [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 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, 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 non-experts: [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 non-experts: [show]
    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).
  • The Adversarial Noise Threshold for Distributed Protocols.
    With Leonard J. Schulman. In SODA 2016, pages 240 - 258.
    Summary for curious non-experts: [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.
Other textual output:
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 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 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 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)