Bill Fefferman

61 papers A* 4A 11B 1Journal 40Unranked 3

Year	Rank	Type	Title / Venue / Authors
2026	A	`conf`	Anti-Concentration for the Unitary Haar Measure and Applications to Random Quantum Circuits. ITCS Bill Fefferman, Soumik Ghosh, Wei Zhan
2026	J	`jnl`	On Certified Randomness from Fourier Sampling or Random Circuit Sampling. Quantum Roozbeh Bassirian, Adam Bouland, Bill Fefferman, Sam Gunn, Avishay Tal
2026	A	`conf`	The Hardness of Learning Quantum Circuits and Its Cryptographic Applications. ITCS Bill Fefferman, Soumik Ghosh, Makrand Sinha, Henry Yuen
2025	—	`ed.`	20th Conference on the Theory of Quantum Computation, Communication and Cryptography, TQC 2025, Indian Institute of Science, Bengaluru, India, September 15-19, 2025 TQC Bill Fefferman
2025	A*	`conf`	Exponential improvements to the average-case hardness of BosonSampling. FOCS Adam Bouland, Ishaun Datta, Bill Fefferman, Felipe Hernandez
2025	J	`jnl`	On the Complexity of Decoded Quantum Interferometry. CoRR Kunal Marwaha, Bill Fefferman, Alexandru Gheorghiu, Vojtech Havlícek
2025	J	`jnl`	Peaked quantum advantage using error correction. CoRR Abhinav Deshpande, Bill Fefferman, Soumik Ghosh, Michael J. Gullans, Dominik Hangleiter
2025	J	`jnl`	The Hardness of Learning Quantum Circuits and its Cryptographic Applications. CoRR Bill Fefferman, Soumik Ghosh, Makrand Sinha, Henry Yuen
2025	J	`jnl`	The Hardness of Learning Quantum Circuits and its Cryptographic Applications. IACR Cryptol. ePrint Arch. Bill Fefferman, Soumik Ghosh, Makrand Sinha, Henry Yuen
2024	J	`jnl`	Anti-Concentration for the Unitary Haar Measure and Applications to Random Quantum Circuits. CoRR Bill Fefferman, Soumik Ghosh, Wei Zhan
2024	J	`jnl`	Anti-Concentration for the Unitary Haar Measure and Applications to Random Quantum Circuits. Electron. Colloquium Comput. Complex. Bill Fefferman, Soumik Ghosh, Wei Zhan
2024	J	`jnl`	On the average-case hardness of BosonSampling. CoRR Adam Bouland, Ishaun Datta, Bill Fefferman, Felipe Hernandez
2024	A	`conf`	Public-Key Pseudoentanglement and the Hardness of Learning Ground State Entanglement Structure. CCC Adam Bouland, Bill Fefferman, Soumik Ghosh, Tony Metger, Umesh V. Vazirani, Chenyi Zhang, Zixin Zhou
2024	A	`conf`	Quantum Merlin-Arthur and Proofs Without Relative Phase. ITCS Roozbeh Bassirian, Bill Fefferman, Kunal Marwaha
2024	J	`jnl`	Quantum Merlin-Arthur with an internally separable proof. CoRR Roozbeh Bassirian, Bill Fefferman, Itai Leigh, Kunal Marwaha, Pei Wu
2024	A	`conf`	Quantum Pseudoentanglement. ITCS Scott Aaronson, Adam Bouland, Bill Fefferman, Soumik Ghosh, Umesh V. Vazirani, Chenyi Zhang, Zixin Zhou
2023	J	`jnl`	Complexity-theoretic foundations of BosonSampling with a linear number of modes. CoRR Adam Bouland, Daniel Jost Brod, Ishaun Datta, Bill Fefferman, Daniel Grier, Felipe Hernandez, Michal Oszmaniec
2023	J	`jnl`	Effect of non-unital noise on random circuit sampling. CoRR Bill Fefferman, Soumik Ghosh, Michael J. Gullans, Kohdai Kuroiwa, Kunal Sharma
2023	—	`conf`	On the Power of Nonstandard Quantum Oracles. TQC Roozbeh Bassirian, Bill Fefferman, Kunal Marwaha
2023	J	`jnl`	Public-key pseudoentanglement and the hardness of learning ground state entanglement structure. CoRR Adam Bouland, Bill Fefferman, Soumik Ghosh, Tony Metger, Umesh V. Vazirani, Chenyi Zhang, Zixin Zhou
2023	J	`jnl`	Quantum Merlin-Arthur and proofs without relative phase. CoRR Roozbeh Bassirian, Bill Fefferman, Kunal Marwaha
2022	J	`jnl`	On the power of nonstandard quantum oracles. CoRR Roozbeh Bassirian, Bill Fefferman, Kunal Marwaha
2022	J	`jnl`	Quantum Pseudoentanglement. CoRR Adam Bouland, Bill Fefferman, Soumik Ghosh, Umesh V. Vazirani, Zixin Zhou
2022	J	`jnl`	Sharp complexity phase transitions generated by entanglement. CoRR Soumik Ghosh, Abhinav Deshpande, Dominik Hangleiter, Alexey V. Gorshkov, Bill Fefferman
2022	A	`conf`	The Importance of the Spectral Gap in Estimating Ground-State Energies. ITCS Abhinav Deshpande, Alexey V. Gorshkov, Bill Fefferman
2021	J	`jnl`	Electronic Structure in a Fixed Basis is QMA-complete. CoRR Bryan O'Gorman, Sandy Irani, James Whitfield, Bill Fefferman
2021	A*	`conf`	Eliminating intermediate measurements in space-bounded Quantum computation. STOC Bill Fefferman, Zachary Remscrim
2021	A*	`conf`	Noise and the Frontier of Quantum Supremacy. FOCS Adam Bouland, Bill Fefferman, Zeph Landau, Yunchao Liu
2021	J	`jnl`	Noise and the frontier of quantum supremacy. CoRR Adam Bouland, Bill Fefferman, Zeph Landau, Yunchao Liu
2021	J	`jnl`	Quantum Complexity: Theory and Application (Dagstuhl Seminar 21261). Dagstuhl Reports Bill Fefferman, Sevag Gharibian, Norbert Schuch, Barbara M. Terhal
2020	A	`conf`	Computational Pseudorandomness, the Wormhole Growth Paradox, and Constraints on the AdS/CFT Duality (Abstract). ITCS Adam Bouland, Bill Fefferman, Umesh V. Vazirani
2020	J	`jnl`	Efficient classical simulation of noisy random quantum circuits in one dimension. Quantum Kyungjoo Noh, Liang Jiang, Bill Fefferman
2020	J	`jnl`	Eliminating Intermediate Measurements in Space-Bounded Quantum Computation. CoRR Bill Fefferman, Zachary Remscrim
2020	J	`jnl`	Eliminating Intermediate Measurements in Space-Bounded Quantum Computation. Electron. Colloquium Comput. Complex. Bill Fefferman, Zachary Remscrim
2020	J	`jnl`	The importance of the spectral gap in estimating ground-state energies. CoRR Abhinav Deshpande, Alexey V. Gorshkov, Bill Fefferman
2019	A	`conf`	"Quantum Supremacy" and the Complexity of Random Circuit Sampling. ITCS Adam Bouland, Bill Fefferman, Chinmay Nirkhe, Umesh V. Vazirani
2019	J	`jnl`	Complexity phase diagram for interacting and long-range bosonic Hamiltonians. CoRR Nishad Maskara, Abhinav Deshpande, Minh C. Tran, Adam Ehrenberg, Bill Fefferman, Alexey V. Gorshkov
2019	J	`jnl`	Computational pseudorandomness, the wormhole growth paradox, and constraints on the AdS/CFT duality. CoRR Adam Bouland, Bill Fefferman, Umesh V. Vazirani
2018	A	`conf`	A Complete Characterization of Unitary Quantum Space. ITCS Bill Fefferman, Cedric Yen-Yu Lin
2018	J	`jnl`	Quantum Supremacy and the Complexity of Random Circuit Sampling. CoRR Adam Bouland, Bill Fefferman, Chinmay Nirkhe, Umesh V. Vazirani
2018	B	`conf`	Quantum vs. Classical Proofs and Subset Verification. MFCS Bill Fefferman, Shelby Kimmel
2017	J	`jnl`	Complexity of sampling as an order parameter. CoRR Abhinav Deshpande, Bill Fefferman, Michael Foss-Feig, Alexey V. Gorshkov
2016	J	`jnl`	A Complete Characterization of Unitary Quantum Space. CoRR Bill Fefferman, Cedric Yen-Yu Lin
2016	—	`conf`	Computational Security of Quantum Encryption. ICITS Gorjan Alagic, Anne Broadbent, Bill Fefferman, Tommaso Gagliardoni, Christian Schaffner, Michael St. Jules
2016	J	`jnl`	Computational Security of Quantum Encryption. CoRR Gorjan Alagic, Anne Broadbent, Bill Fefferman, Tommaso Gagliardoni, Christian Schaffner, Michael St. Jules
2016	J	`jnl`	Computational Security of Quantum Encryption. IACR Cryptol. ePrint Arch. Gorjan Alagic, Anne Broadbent, Bill Fefferman, Tommaso Gagliardoni, Christian Schaffner, Michael St. Jules
2016	J	`jnl`	On Quantum Obfuscation. CoRR Gorjan Alagic, Bill Fefferman
2016	—	`conf`	On the Power of Quantum Fourier Sampling. TQC Bill Fefferman, Christopher Umans
2016	J	`jnl`	Quantum Merlin Arthur with Exponentially Small Gap. CoRR Bill Fefferman, Cedric Yen-Yu Lin
2016	A*	`conf`	Space-Efficient Error Reduction for Unitary Quantum Computations. ICALP Bill Fefferman, Hirotada Kobayashi, Cedric Yen-Yu Lin, Tomoyuki Morimae, Harumichi Nishimura
2016	J	`jnl`	Space-Efficient Error Reduction for Unitary Quantum Computations. CoRR Bill Fefferman, Hirotada Kobayashi, Cedric Yen-Yu Lin, Tomoyuki Morimae, Harumichi Nishimura
2015	J	`jnl`	Quantum vs Classical Proofs and Subset Verification. CoRR Bill Fefferman, Shelby Kimmel
2015	J	`jnl`	The Power of Quantum Fourier Sampling. CoRR Bill Fefferman, Chris Umans
2014	—	`—`	The Power of Quantum Fourier Sampling. Bill Fefferman
2013	J	`jnl`	On Beating the Hybrid Argument. Theory Comput. Bill Fefferman, Ronen Shaltiel, Christopher Umans, Emanuele Viola
2012	A	`conf`	On beating the hybrid argument. ITCS Bill Fefferman, Ronen Shaltiel, Christopher Umans, Emanuele Viola
2010	J	`jnl`	On beating the hybrid argument. Electron. Colloquium Comput. Complex. Bill Fefferman, Ronen Shaltiel, Christopher Umans, Emanuele Viola
2010	J	`jnl`	Pseudorandom generators and the BQP vs. PH problem CoRR Bill Fefferman, Christopher Umans
2009	J	`jnl`	The Power of Unentanglement. Theory Comput. Scott Aaronson, Salman Beigi, Andrew Drucker, Bill Fefferman, Peter W. Shor
2008	A	`conf`	The Power of Unentanglement. CCC Scott Aaronson, Salman Beigi, Andrew Drucker, Bill Fefferman, Peter W. Shor
2008	J	`jnl`	The Power of Unentanglement. Electron. Colloquium Comput. Complex. Scott Aaronson, Salman Beigi, Andrew Drucker, Bill Fefferman, Peter W. Shor