Publications

1.  The Power of Unentanglement

with S. Aaronson, S. Beigi, A. Drucker, P. Shor

In Theory of Computing Journal, 5(1):1-42, 2009. [ToC]

In Proceedings of IEEE Conference on Computational Complexity 2008 [Conference abstractarXiv]

2.  Pseudorandom Generators and the BQP vs PH Problem

with C. Umans

Accepted to Conference on Quantum Information Processing (QIP 2011) as a featured talk [pdf, arXiv]

3.  On Beating the Hybrid Argument

with R. Shaltiel, C. Umans and E.Viola

In Theory of Computing Journal, 9(26):809-843, 2013. [ToC]

In Proceedings of Innovations in Theoretical Computer Science (ITCS 2012) [ECCC, Conference abstract]

4.   On The Power of Quantum Fourier Sampling

with C. Umans

In Proceedings of Theory of Quantum Computation, Communication, and Cryptography (TQC 2016)  [pdfarXiv]

5.  Quantum vs Classical Proofs and Subset Verification

with S. Kimmel

Submitted [pdfarXiv]

6.   Quantum Merlin Arthur with Exponentially Small Gap

with C. Lin

Draft [pdfarXiv]

7.   On Quantum Obfuscation

with G. Alagic

Accepted talk at International Conference on Quantum Cryptography (QCrypt 2016) [pdfarXiv]

8.   Computational Security of Quantum Encryption

with G. Alagic, A. Broadbent, T. Gagliardoni, C. Schaffner, and M. St. Jules

Accepted talk at International Conference on Quantum Cryptography (QCrypt 2016).

In Proceedings of International Conference on Information Theoretic Security (ICITS 2016) [pdfarXiv]

9.   A Complete Characterization of Unitary Quantum Space

with C. Lin

Accepted talk at Conference on Quantum Information Processing (QIP 2017) [pdfarXiv]

10.   Space-Efficient Error Reduction for Unitary Quantum Computations

with H. Kobayashi, C. Lin, T. Morimae, and H. Nishimura

Accepted talk at Asian Quantum Information Science Conference (AQIS 2016).

In Proceedings of International Colloquium on Automata, Languages and Programming (ICALP 2016) [pdfarXiv]

11.  Exact Sampling Hardness of Ising Spin Models

with M. Foss-Feig, A.V. Gorshkov

Draft [pdfarXiv]

12.  Complexity of Sampling as an Order Parameter

with A. Deshpande, M. Foss-Feig, A.V. Gorshkov

Draft [pdfarXiv]