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. Previously, I was an undergrad in Mathematics with Computer Science at MIT.

I am broadly interested in quantum and classical complexity theory. Currently, my research focuses on studying limits of computation via symmetries of polynomials.

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. Lower Bounding the AND-OR Tree via Symmetrization
   William Kretschmer
   [arXiv]
2. Quantum Lower Bounds for Approximate Counting via Laurent Polynomials
   Scott Aaronson, Robin Kothari, William Kretschmer, Justin Thaler
   Subsumes arXiv:1808.02420 by Scott Aaronson and arXiv:1902.02398 by William Kretschmer
   [arXiv] [ECCC]
3. Simulation of Qubit Quantum Circuits via Pauli Propagation
   Patrick Rall, Daniel Liang, Jeremy Cook, William Kretschmer
   Physical Review A 99, 062337 (2019)
   [arXiv] [Journal]
4. 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)
   [PMLR]
5. Groups in Circle Puzzles
   William Kretschmer
   Game and Puzzle Design 3:2, 15-26 (2017)
   [Journal]

Last updated: July 16, 2019