William Kretschmer

According to our database, William Kretschmer authored at least 22 papers between 2016 and 2025.

Collaborative distances:

• Dijkstra number of four.
• Erdős number of three.

2025

Unentanglement and Post-Measurement Branching in Quantum Interactive Proofs.

Sabee Grewal, William Kretschmer

CoRR, September, 2025

Quantum-Computable One-Way Functions without One-Way Functions.

William Kretschmer, Luowen Qian, Avishay Tal

Proceedings of the 57th Annual ACM Symposium on Theory of Computing, 2025

Learning the Closest Product State.

Ainesh Bakshi, John Bostanci, William Kretschmer, Zeph Landau, Jerry Li, Allen Liu, Ryan O'Donnell, Ewin Tang

Proceedings of the 57th Annual ACM Symposium on Theory of Computing, 2025

2024

Agnostic Tomography of Stabilizer Product States.

Sabee Grewal, Vishnu Iyer, William Kretschmer, Daniel Liang

CoRR, 2024

Pseudoentanglement Ain't Cheap.

Sabee Grewal, Vishnu Iyer, William Kretschmer, Daniel Liang

CoRR, 2024

Improved Stabilizer Estimation via Bell Difference Sampling.

Sabee Grewal, Vishnu Iyer, William Kretschmer, Daniel Liang

Proceedings of the 56th Annual ACM Symposium on Theory of Computing, 2024

A Qubit, a Coin, and an Advice String Walk into a Relational Problem.

Scott Aaronson, Harry Buhrman, William Kretschmer

Proceedings of the 15th Innovations in Theoretical Computer Science Conference, 2024

2023

Efficient Learning of Quantum States Prepared With Few Non-Clifford Gates.

Sabee Grewal, Vishnu Iyer, William Kretschmer, Daniel Liang

CoRR, 2023

Two-Disk Compound Symmetry Groups.

Robert A. Hearn, William Kretschmer, Tomas Rokicki, Benjamin Streeter, Eric Vergo

CoRR, 2023

Quantum Mass Production Theorems.

William Kretschmer

Proceedings of the 18th Conference on the Theory of Quantum Computation, 2023

Quantum Cryptography in Algorithmica.

William Kretschmer, Luowen Qian, Makrand Sinha, Avishay Tal

Proceedings of the 55th Annual ACM Symposium on Theory of Computing, 2023

Low-Stabilizer-Complexity Quantum States Are Not Pseudorandom.

Sabee Grewal, Vishnu Iyer, William Kretschmer, Daniel Liang

Proceedings of the 14th Innovations in Theoretical Computer Science Conference, 2023

2022

The Acrobatics of BQP.

Scott Aaronson, DeVon Ingram, William Kretschmer

Proceedings of the 37th Computational Complexity Conference, 2022

2021

Lower Bounding the AND-OR Tree via Symmetrization.

William Kretschmer

ACM Trans. Comput. Theory, 2021

Quantum Pseudorandomness and Classical Complexity.

William Kretschmer

Proceedings of the 16th Conference on the Theory of Quantum Computation, 2021

The Quantum Supremacy Tsirelson Inequality.

William Kretschmer

Proceedings of the 12th Innovations in Theoretical Computer Science Conference, 2021

2020

Symmetries, Graph Properties, and Quantum Speedups.

Shalev Ben-David, Andrew M. Childs, András Gilyén, William Kretschmer, Supartha Podder, Daochen Wang

Proceedings of the 61st IEEE Annual Symposium on Foundations of Computer Science, 2020

Quantum Lower Bounds for Approximate Counting via Laurent Polynomials.

Scott Aaronson, Robin Kothari, William Kretschmer, Justin Thaler

Proceedings of the 35th Computational Complexity Conference, 2020

2019

QMA Lower Bounds for Approximate Counting.

William Kretschmer

Electron. Colloquium Comput. Complex., 2019

$\mathsf{QMA}$ Lower Bounds for Approximate Counting.

William Kretschmer

CoRR, 2019

2018

Structured Factored Inference for Probabilistic Programming.

Avi Pfeffer, Brian E. Ruttenberg, William Kretschmer, Alison O'Connor

Proceedings of the International Conference on Artificial Intelligence and Statistics, 2018

2016

Structured Factored Inference: A Framework for Automated Reasoning in Probabilistic Programming Languages.

Avi Pfeffer, Brian E. Ruttenberg, William Kretschmer

CoRR, 2016