Vannevar Bush Faculty Fellow
PECASE Award

I'm a Professor of Computer Science and Engineering at Penn State University.  Prior to coming to Penn State, I was a Senior Research Staff Member and Head of the Quantum Information Technology group at NEC Laboratories in Princeton.  Before that I was an NSF Mathematical Sciences Postdoctoral Fellow at Caltech and the Institute for Quantum Information, and a postdoctoral fellow at the Mathematical Sciences Research Institute in Berkeley.  I have a Ph.D. in computer science from the University of California, Berkeley, and a B.S. in computer science from Carnegie Mellon University.

Papers:

• An efficient quantum algorithm for lattice problems achieving subexponential approximation factor, with Lior Eldar.
• arxiv.org/abs/2201.13450
  
• Limitations of the Macaulay matrix approach for using the HHL algorithm to solve multivariate polynomial systems, with Jintai Ding, Vlad Gheorghiu, Andras Gilyen, and Jianqiang Li.
• QIP 2021, link.
  
• Computing endomorphism rings of supersingular elliptic curves and connections to path-finding in isogeny graph problems, with Kirsten Eisenträger, Chris Leonardi, Travis Morrison, and Jennifer Park.
• ANTS-XIV 2020, link.
  
• An approximation algorithm for the MAX-2-Local Hamiltonian problem, with Eunou Lee and Ojas Parekh.
• APPROX 2020, link, talk at QIP 2020, pdf.
  
• On basing one-way permutations on NP-hard problems under quantum reductions, with Nai-Hui Chia and Fang Song,
• Quantum 4, 312(2020), link.  Talk at QCRYPT 2018, arxiv.
  
• Supersingular isogeny graphs and endomorphism rings: reductions and solutions, with Kirsten Eisenträger, Kristin Lauter, Travis Morrison, and Christophe Petit,
• EUROCRYPT 2018.  link
  
• How Hard is Deciding Trivial versus Nontrivial in the Dihedral Coset Problem?, with Nai-Hui Chia,
• TQC 2016.  pdf
  
• Weak Instances of PLWE, with Kirsten Eisenträger and Kristin Lauter,
• SAC 2014.  link
  
• A quantum algorithm for computing the unit group of an arbitrary degree number field,  with Kirsten Eisenträger, Alexei Kitaev, and Fang Song,
• STOC 2014.  Submission version 11/11/2013.  Full version in progress 2019.
  
• The Local Hamiltonian problem on a line with eight states is QMA-Complete, with Daniel Nagaj and Sandeep Narayanaswami,
• Quantum Information & Computation, Vol. 13, No. 9&10, 2013.  arxiv
  
• Computing the unit group, class group, and compact representations in algebraic function fields, with Kirsten Eisenträger,
• ANTS-X 2012.  link
  
• Classical Cryptographic Protocols in a Quantum World, with Adam Smith and Fang Song,
• International Journal of Quantum Information, Vol. 13, No. 4, 2015.  arxiv
  
• CRYPTO 2011.  pdf
  
• Algorithms for ray class groups and Hilbert class fields, with Kirsten Eisenträger,
• SODA 2010.  pdf
  
• Superpolynomial speedups based on almost any quantum circuit, with Aram Harrow,
• ICALP 2008.  arxiv
  
• Making classical honest verifier zero knowledge protocols secure against quantum attacks, with Alexandra Kolla, Pranab Sen, and Shengyu Zhang,
• ICALP 2008.  Best paper Track C.
  
• Limitations of Quantum Coset States for Graph Isomorphism, with Cristopher Moore, Martin Roetteler, Alexander Russell, and Pranab Sen,
• STOC 2006.
  
• Journal of the ACM, 57(6), article 34, 2010.  pdf
  
• Fast Quantum Algorithms for Computing the Unit Group and Class Group of a Number Field,
• STOC 2005.  pdf
  
• Quantum Noisy Rational Function Reconstruction, with Alexander Russell and Igor Shparlinski,
• COCOON 2005.
• Quantum Algorithms for some Hidden Shift Problems, with Wim van Dam and Lawrence Ip,
• SODA 2003.  arxiv
  
• SIAM Journal on Computing, 36(3):763-778, 2006.   pdf
  
• Polynomial-Time Quantum Algorithms for Pell's Equation and the Principal Ideal Problem,
• STOC 2002.   pdf
• Journal of the ACM, 54(1):1-19, 2007.
  
• Quantum Fourier Sampling, the Hidden Subgroup Problem, and Beyond,
  
• Ph.D. Thesis, University of California, Berkeley, 2000.  pdf   (Chapters ) 
  
• An Improved Quantum Fourier Transform Algorithm and Applications, with Lisa Hales,
• FOCS 2000.
• Normal Subgroup Reconstruction and Quantum Computation Using Group Representations , with Alexander Russell and Amnon Ta-Shma,
• STOC 2000.   pdf
• SIAM Journal on Computing, 32(4):916-934, 2003.  pdf
  
• Quantum Fourier Sampling Simplified, with Lisa Hales,
• STOC 1999.

• Theory of Computation, Spring 2011, 2018, Fall 2011, 2014, 2015, 2016, 2020
  
• Introduction to Cryptography, Fall 2019
  
• Topics in Post-Quantum Cryptography, Fall 2018
  
• Computational Complexity, Fall 2010, Spring 2016
  
• Algorithm Design and Analysis, Fall 2009, 2012, 2017
  
• Discrete Mathematics, Spring/Fall 2008
  
• Quantum Computation, Fall 2007, Spring 2010, 2012, 2013, 2015, 2017, 2018, 2021
• Theory of Computation, Princeton University, Fall 2006

My old team