Bill Fefferman

According to our database, Bill Fefferman authored at least 36 papers between 2008 and 2025.

Collaborative distances:

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

2025

Peaked quantum advantage using error correction.

Abhinav Deshpande, Bill Fefferman, Soumik Ghosh, Michael J. Gullans, Dominik Hangleiter

CoRR, October, 2025

On the Complexity of Decoded Quantum Interferometry.

Kunal Marwaha, Bill Fefferman, Alexandru Gheorghiu, Vojtech Havlícek

CoRR, September, 2025

The Hardness of Learning Quantum Circuits and its Cryptographic Applications.

Bill Fefferman, Soumik Ghosh, Makrand Sinha, Henry Yuen

IACR Cryptol. ePrint Arch., 2025

2024

Anti-Concentration for the Unitary Haar Measure and Applications to Random Quantum Circuits.

Bill Fefferman, Soumik Ghosh, Wei Zhan

Electron. Colloquium Comput. Complex., 2024

On the average-case hardness of BosonSampling.

Adam Bouland, Ishaun Datta, Bill Fefferman, Felipe Hernandez

CoRR, 2024

Quantum Merlin-Arthur with an internally separable proof.

Roozbeh Bassirian, Bill Fefferman, Itai Leigh, Kunal Marwaha, Pei Wu

CoRR, 2024

Quantum Merlin-Arthur and Proofs Without Relative Phase.

Roozbeh Bassirian, Bill Fefferman, Kunal Marwaha

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

Quantum Pseudoentanglement.

Scott Aaronson, Adam Bouland, Bill Fefferman, Soumik Ghosh, Umesh V. Vazirani, Chenyi Zhang, Zixin Zhou

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

Public-Key Pseudoentanglement and the Hardness of Learning Ground State Entanglement Structure.

Adam Bouland, Bill Fefferman, Soumik Ghosh, Tony Metger, Umesh V. Vazirani, Chenyi Zhang, Zixin Zhou

Proceedings of the 39th Computational Complexity Conference, 2024

2023

Complexity-theoretic foundations of BosonSampling with a linear number of modes.

Adam Bouland, Daniel Jost Brod, Ishaun Datta, Bill Fefferman, Daniel Grier, Felipe Hernandez, Michal Oszmaniec

CoRR, 2023

Effect of non-unital noise on random circuit sampling.

Bill Fefferman, Soumik Ghosh, Michael J. Gullans, Kohdai Kuroiwa, Kunal Sharma

CoRR, 2023

On the Power of Nonstandard Quantum Oracles.

Roozbeh Bassirian, Bill Fefferman, Kunal Marwaha

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

2022

Sharp complexity phase transitions generated by entanglement.

Soumik Ghosh, Abhinav Deshpande, Dominik Hangleiter, Alexey V. Gorshkov, Bill Fefferman

CoRR, 2022

Quantum Pseudoentanglement.

Adam Bouland, Bill Fefferman, Soumik Ghosh, Umesh V. Vazirani, Zixin Zhou

CoRR, 2022

The Importance of the Spectral Gap in Estimating Ground-State Energies.

Abhinav Deshpande, Alexey V. Gorshkov, Bill Fefferman

Proceedings of the 13th Innovations in Theoretical Computer Science Conference, 2022

2021

Quantum Complexity: Theory and Application (Dagstuhl Seminar 21261).

Bill Fefferman, Sevag Gharibian, Norbert Schuch, Barbara M. Terhal

Dagstuhl Reports, 2021

Electronic Structure in a Fixed Basis is QMA-complete.

Bryan O'Gorman, Sandy Irani, James Whitfield, Bill Fefferman

CoRR, 2021

Eliminating intermediate measurements in space-bounded Quantum computation.

Bill Fefferman, Zachary Remscrim

Proceedings of the STOC '21: 53rd Annual ACM SIGACT Symposium on Theory of Computing, 2021

Noise and the Frontier of Quantum Supremacy.

Adam Bouland, Bill Fefferman, Zeph Landau, Yunchao Liu

Proceedings of the 62nd IEEE Annual Symposium on Foundations of Computer Science, 2021

2020

Efficient classical simulation of noisy random quantum circuits in one dimension.

Kyungjoo Noh, Liang Jiang, Bill Fefferman

Quantum, 2020

Computational Pseudorandomness, the Wormhole Growth Paradox, and Constraints on the AdS/CFT Duality (Abstract).

Adam Bouland, Bill Fefferman, Umesh V. Vazirani

Proceedings of the 11th Innovations in Theoretical Computer Science Conference, 2020

2019

Computational pseudorandomness, the wormhole growth paradox, and constraints on the AdS/CFT duality.

Adam Bouland, Bill Fefferman, Umesh V. Vazirani

CoRR, 2019

Complexity phase diagram for interacting and long-range bosonic Hamiltonians.

Nishad Maskara, Abhinav Deshpande, Minh C. Tran, Adam Ehrenberg, Bill Fefferman, Alexey V. Gorshkov

CoRR, 2019

"Quantum Supremacy" and the Complexity of Random Circuit Sampling.

Adam Bouland, Bill Fefferman, Chinmay Nirkhe, Umesh V. Vazirani

Proceedings of the 10th Innovations in Theoretical Computer Science Conference, 2019

2018

Quantum vs. Classical Proofs and Subset Verification.

Bill Fefferman, Shelby Kimmel

Proceedings of the 43rd International Symposium on Mathematical Foundations of Computer Science, 2018

A Complete Characterization of Unitary Quantum Space.

Bill Fefferman, Cedric Yen-Yu Lin

Proceedings of the 9th Innovations in Theoretical Computer Science Conference, 2018

2017

Complexity of sampling as an order parameter.

Abhinav Deshpande, Bill Fefferman, Michael Foss-Feig, Alexey V. Gorshkov

CoRR, 2017

2016

Quantum Merlin Arthur with Exponentially Small Gap.

Bill Fefferman, Cedric Yen-Yu Lin

CoRR, 2016

On Quantum Obfuscation.

Gorjan Alagic, Bill Fefferman

CoRR, 2016

On the Power of Quantum Fourier Sampling.

Bill Fefferman, Christopher Umans

Proceedings of the 11th Conference on the Theory of Quantum Computation, 2016

Computational Security of Quantum Encryption.

Gorjan Alagic, Anne Broadbent, Bill Fefferman, Tommaso Gagliardoni, Christian Schaffner, Michael St. Jules

Proceedings of the Information Theoretic Security - 9th International Conference, 2016

Space-Efficient Error Reduction for Unitary Quantum Computations.

Bill Fefferman, Hirotada Kobayashi, Cedric Yen-Yu Lin, Tomoyuki Morimae, Harumichi Nishimura

Proceedings of the 43rd International Colloquium on Automata, Languages, and Programming, 2016

2014

The Power of Quantum Fourier Sampling.

Bill Fefferman

PhD thesis, 2014

2012

On beating the hybrid argument.

Bill Fefferman, Ronen Shaltiel, Christopher Umans, Emanuele Viola

Proceedings of the Innovations in Theoretical Computer Science 2012, 2012

2010

Pseudorandom generators and the BQP vs. PH problem

Bill Fefferman, Christopher Umans

CoRR, 2010

2008

The Power of Unentanglement.

Scott Aaronson, Salman Beigi, Andrew Drucker, Bill Fefferman, Peter W. Shor

Proceedings of the 23rd Annual IEEE Conference on Computational Complexity, 2008