William Kretschmer

42 papers A* 5A 6Journal 29Unranked 2

Year	Rank	Type	Title / Venue / Authors
2026	J	`jnl`	Agnostic Tomography of Stabilizer Product States. Quantum Sabee Grewal, Vishnu Iyer, William Kretschmer, Daniel Liang
2025	J	`jnl`	Efficient Learning of Quantum States Prepared With Few Non-Clifford Gates. Quantum Sabee Grewal, Vishnu Iyer, William Kretschmer, Daniel Liang
2025	A*	`conf`	Learning the Closest Product State. STOC Ainesh Bakshi, John Bostanci, William Kretschmer, Zeph Landau, Jerry Li, Allen Liu, Ryan O'Donnell, Ewin Tang
2025	A*	`conf`	Quantum-Computable One-Way Functions without One-Way Functions. STOC William Kretschmer, Luowen Qian, Avishay Tal
2025	J	`jnl`	Unentanglement and Post-Measurement Branching in Quantum Interactive Proofs. CoRR Sabee Grewal, William Kretschmer
2025	J	`jnl`	Unentanglement and Post-Measurement Branching in Quantum Interactive Proofs. Electron. Colloquium Comput. Complex. Sabee Grewal, William Kretschmer
2024	A	`conf`	A Qubit, a Coin, and an Advice String Walk into a Relational Problem. ITCS Scott Aaronson, Harry Buhrman, William Kretschmer
2024	J	`jnl`	Agnostic Tomography of Stabilizer Product States. CoRR Sabee Grewal, Vishnu Iyer, William Kretschmer, Daniel Liang
2024	A*	`conf`	Improved Stabilizer Estimation via Bell Difference Sampling. STOC Sabee Grewal, Vishnu Iyer, William Kretschmer, Daniel Liang
2024	J	`jnl`	Pseudoentanglement Ain't Cheap. CoRR Sabee Grewal, Vishnu Iyer, William Kretschmer, Daniel Liang
2024	J	`jnl`	Quantum-Computable One-Way Functions without One-Way Functions. CoRR William Kretschmer, Luowen Qian, Avishay Tal
2024	J	`jnl`	Symmetries, Graph Properties, and Quantum Speedups. SIAM J. Comput. Shalev Ben-David, Andrew M. Childs, András Gilyén, William Kretschmer, Supartha Podder, Daochen Wang
2023	J	`jnl`	A Qubit, a Coin, and an Advice String Walk Into a Relational Problem. CoRR Scott Aaronson, Harry Buhrman, William Kretschmer
2023	J	`jnl`	A Qubit, a Coin, and an Advice String Walk Into a Relational Problem. Electron. Colloquium Comput. Complex. Scott Aaronson, Harry Buhrman, William Kretschmer
2023	J	`jnl`	Efficient Learning of Quantum States Prepared With Few Non-Clifford Gates. CoRR Sabee Grewal, Vishnu Iyer, William Kretschmer, Daniel Liang
2023	J	`jnl`	Improved Stabilizer Estimation via Bell Difference Sampling. CoRR Sabee Grewal, Vishnu Iyer, William Kretschmer, Daniel Liang
2023	A	`conf`	Low-Stabilizer-Complexity Quantum States Are Not Pseudorandom. ITCS Sabee Grewal, Vishnu Iyer, William Kretschmer, Daniel Liang
2023	A*	`conf`	Quantum Cryptography in Algorithmica. STOC William Kretschmer, Luowen Qian, Makrand Sinha, Avishay Tal
2023	—	`conf`	Quantum Mass Production Theorems. TQC William Kretschmer
2023	J	`jnl`	Two-Disk Compound Symmetry Groups. CoRR Robert A. Hearn, William Kretschmer, Tomas Rokicki, Benjamin Streeter, Eric Vergo
2022	J	`jnl`	Low-Stabilizer-Complexity Quantum States Are Not Pseudorandom. CoRR Sabee Grewal, Vishnu Iyer, William Kretschmer, Daniel Liang
2022	J	`jnl`	Quantum Cryptography in Algorithmica. CoRR William Kretschmer, Luowen Qian, Makrand Sinha, Avishay Tal
2022	J	`jnl`	Quantum Mass Production Theorems. CoRR William Kretschmer
2022	A	`conf`	The Acrobatics of BQP. CCC Scott Aaronson, DeVon Ingram, William Kretschmer
2021	J	`jnl`	Lower Bounding the AND-OR Tree via Symmetrization. ACM Trans. Comput. Theory William Kretschmer
2021	—	`conf`	Quantum Pseudorandomness and Classical Complexity. TQC William Kretschmer
2021	J	`jnl`	Quantum Pseudorandomness and Classical Complexity. CoRR William Kretschmer
2021	J	`jnl`	The Acrobatics of BQP. CoRR Scott Aaronson, DeVon Ingram, William Kretschmer
2021	J	`jnl`	The Acrobatics of BQP. Electron. Colloquium Comput. Complex. Scott Aaronson, DeVon Ingram, William Kretschmer
2021	A	`conf`	The Quantum Supremacy Tsirelson Inequality. ITCS William Kretschmer
2021	J	`jnl`	The Quantum Supremacy Tsirelson Inequality. Quantum William Kretschmer
2020	A	`conf`	Quantum Lower Bounds for Approximate Counting via Laurent Polynomials. CCC Scott Aaronson, Robin Kothari, William Kretschmer, Justin Thaler
2020	A*	`conf`	Symmetries, Graph Properties, and Quantum Speedups. FOCS Shalev Ben-David, Andrew M. Childs, András Gilyén, William Kretschmer, Supartha Podder, Daochen Wang
2020	J	`jnl`	Symmetries, graph properties, and quantum speedups. CoRR Shalev Ben-David, Andrew M. Childs, András Gilyén, William Kretschmer, Supartha Podder, Daochen Wang
2020	J	`jnl`	The Quantum Supremacy Tsirelson Inequality. CoRR William Kretschmer
2019	J	`jnl`	$\mathsf{QMA}$ Lower Bounds for Approximate Counting. CoRR William Kretschmer
2019	J	`jnl`	Lower Bounding the AND-OR Tree via Symmetrization. CoRR William Kretschmer
2019	J	`jnl`	QMA Lower Bounds for Approximate Counting. Electron. Colloquium Comput. Complex. William Kretschmer
2019	J	`jnl`	Quantum Lower Bounds for Approximate Counting via Laurent Polynomials. CoRR Scott Aaronson, Robin Kothari, William Kretschmer, Justin Thaler
2019	J	`jnl`	Quantum Lower Bounds for Approximate Counting via Laurent Polynomials. Electron. Colloquium Comput. Complex. Scott Aaronson, Robin Kothari, William Kretschmer, Justin Thaler
2018	A	`conf`	Structured Factored Inference for Probabilistic Programming. AISTATS Avi Pfeffer, Brian E. Ruttenberg, William Kretschmer, Alison O'Connor
2016	J	`jnl`	Structured Factored Inference: A Framework for Automated Reasoning in Probabilistic Programming Languages. CoRR Avi Pfeffer, Brian E. Ruttenberg, William Kretschmer