We stand with Ukraine  

William Kretschmer

Orcid: 0000-0002-7784-9817

Affiliations:
  • University of California, Berkeley USA
  • University of Texas at Austin, TX, USA (former)


According to our database1, William Kretschmer authored at least 21 papers between 2016 and 2025.

Collaborative distances:

Timeline

Legend:

Book 
In proceedings 
Article 
PhD thesis 
Dataset
Other 

Links

Online presence:

On csauthors.net:

Bibliography

2025
Quantum-Computable One-Way Functions without One-Way Functions.
[BibTeX]
[DOI]
William Kretschmer
,
Luowen Qian
,
Avishay Tal
Proceedings of the 57th Annual ACM Symposium on Theory of Computing, 2025

Learning the Closest Product State.
[BibTeX]
[DOI]
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
Symmetries, Graph Properties, and Quantum Speedups.
[BibTeX]
[DOI]
Shalev Ben-David
,
Andrew M. Childs
,
András Gilyén
,
William Kretschmer
,
Supartha Podder
,
Daochen Wang
SIAM J. Comput., 2024

Agnostic Tomography of Stabilizer Product States.
[BibTeX]
[DOI]
Sabee Grewal
,
Vishnu Iyer
,
William Kretschmer
,
Daniel Liang
CoRR, 2024

Pseudoentanglement Ain't Cheap.
[BibTeX]
[DOI]
Sabee Grewal
,
Vishnu Iyer
,
William Kretschmer
,
Daniel Liang
CoRR, 2024

Improved Stabilizer Estimation via Bell Difference Sampling.
[BibTeX]
[DOI]
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.
[BibTeX]
[DOI]
Scott Aaronson
,
Harry Buhrman
,
William Kretschmer
Electron. Colloquium Comput. Complex., 2023

Efficient Learning of Quantum States Prepared With Few Non-Clifford Gates.
[BibTeX]
[DOI]
Sabee Grewal
,
Vishnu Iyer
,
William Kretschmer
,
Daniel Liang
CoRR, 2023

Two-Disk Compound Symmetry Groups.
[BibTeX]
[DOI]
Robert A. Hearn
,
William Kretschmer
,
Tomas Rokicki
,
Benjamin Streeter
,
Eric Vergo
CoRR, 2023

Quantum Mass Production Theorems.
[BibTeX]
[DOI]
William Kretschmer
Proceedings of the 18th Conference on the Theory of Quantum Computation, 2023

Quantum Cryptography in Algorithmica.
[BibTeX]
[DOI]
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.
[BibTeX]
[DOI]
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.
[BibTeX]
[DOI]
William Kretschmer
ACM Trans. Comput. Theory, 2021

The Quantum Supremacy Tsirelson Inequality.
[BibTeX]
[DOI]
William Kretschmer
Quantum, 2021

The Acrobatics of BQP.
[BibTeX]
[DOI]
Scott Aaronson
,
DeVon Ingram
,
William Kretschmer
Electron. Colloquium Comput. Complex., 2021

Quantum Pseudorandomness and Classical Complexity.
[BibTeX]
[DOI]
William Kretschmer
Proceedings of the 16th Conference on the Theory of Quantum Computation, 2021

2019
QMA Lower Bounds for Approximate Counting.
[BibTeX]
[DOI]
William Kretschmer
Electron. Colloquium Comput. Complex., 2019

Quantum Lower Bounds for Approximate Counting via Laurent Polynomials.
[BibTeX]
[DOI]
Scott Aaronson
,
Robin Kothari
,
William Kretschmer
,
Justin Thaler
Electron. Colloquium Comput. Complex., 2019

$\mathsf{QMA}$ Lower Bounds for Approximate Counting.
[BibTeX]
[DOI]
William Kretschmer
CoRR, 2019

2018
Structured Factored Inference for Probabilistic Programming.
[BibTeX]
[DOI]
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.
[BibTeX]
[DOI]
Avi Pfeffer
,
Brian E. Ruttenberg
,
William Kretschmer
CoRR, 2016


  Loading...