William Kretschmer

According to our database, William Kretschmer authored at least 19 papers between 2016 and 2024.

Collaborative distances:

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

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

2023

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

Scott Aaronson, Harry Buhrman, William Kretschmer

Electron. Colloquium Comput. Complex., 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

2021

Lower Bounding the AND-OR Tree via Symmetrization.

William Kretschmer

ACM Trans. Comput. Theory, 2021

The Quantum Supremacy Tsirelson Inequality.

William Kretschmer

Quantum, 2021

The Acrobatics of BQP.

Scott Aaronson, DeVon Ingram, William Kretschmer

Electron. Colloquium Comput. Complex., 2021

Quantum Pseudorandomness and Classical Complexity.

William Kretschmer

Proceedings of the 16th Conference on the Theory of Quantum Computation, 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

2019

QMA Lower Bounds for Approximate Counting.

William Kretschmer

Electron. Colloquium Comput. Complex., 2019

Quantum Lower Bounds for Approximate Counting via Laurent Polynomials.

Scott Aaronson, Robin Kothari, William Kretschmer, Justin Thaler

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