William Kretschmer

About

I am a PhD student in Computer Science at UT Austin, where I am fortunate to have Scott Aaronson as my advisor. I am supported by an NDSEG fellowship. Previously, I was an undergrad in Mathematics with Computer Science at MIT.

I am broadly interested in quantum and classical complexity theory. Currently, much of my research focuses on (limitations of) quantum algorithms and (in)ability to apply classical algorithmic techniques in quantum computation.

On the side, I have a large interest in combination puzzles, especially Rubik's-type "twisty puzzles". I have designed more than a dozen unique 3D-printed twisty puzzles, all of which have been shared on the Twisty Puzzles forum, and most of which can be found in the Twisty Puzzles museum. Many of my designs are also available for download.

Email: (first 7 letters of last name, all lowercase)@cs.utexas.edu
Office: GDC 4.504E

Publications

  1. Quantum Pseudorandomness and Classical Complexity
    William Kretschmer
    To appear in TQC 2021.
    [arXiv]
  2. The Quantum Supremacy Tsirelson Inequality
    William Kretschmer
    Presented at the 24th Annual Conference on Quantum Information Processing (QIP 2021)
    12th Innovations in Theoretical Computer Science Conference (ITCS 2021), Leibniz International Proceedings in Informatics (LIPIcs) 185, pp. 13:1–13:13 (2021)
    [arXiv] [ITCS 2021]
  3. Symmetries, graph properties, and quantum speedups
    Shalev Ben-David, Andrew M. Childs, András Gilyén, William Kretschmer, Supartha Podder, Daochen Wang
    Presented at the 24th Annual Conference on Quantum Information Processing (QIP 2021)
    Proceedings of the IEEE 61st Annual Symposium on Foundations of Computer Science (FOCS 2020), pp. 649–660 (2020).
    [arXiv] [FOCS 2020]
  4. Lower Bounding the AND-OR Tree via Symmetrization
    William Kretschmer
    ACM Transactions on Computation Theory 13:1 (2021)
    [arXiv] [Journal]
  5. Quantum Lower Bounds for Approximate Counting via Laurent Polynomials
    Scott Aaronson, Robin Kothari, William Kretschmer, Justin Thaler
    Presented at the 23rd Annual Conference on Quantum Information Processing (QIP 2020)
    35th Computational Complexity Conference (CCC 2020), Leibniz International Proceedings in Informatics (LIPIcs) 169, pp. 7:1–7:47 (2020)
    [arXiv] [ECCC] [CCC 2020]
  6. Simulation of Qubit Quantum Circuits via Pauli Propagation
    Patrick Rall, Daniel Liang, Jeremy Cook, William Kretschmer
    Physical Review A 99, 062337 (2019)
    [arXiv] [Journal]
  7. Structured Factored Inference for Probabilistic Programming
    Avi Pfeffer, Brian Ruttenberg, William Kretschmer, Alison O'Connor
    Proceedings of the 21st International Conference on Artificial Intelligence and Statistics (AISTATS 2018), Proceedings of Machine Learning Research 84, pp. 1224–1232 (2018)
    [PMLR]
  8. Groups in Circle Puzzles
    William Kretschmer
    Game and Puzzle Design 3:2, pp. 15–26 (2017)
    [Journal]
Last updated: May 3, 2021