Sean Hallgren

Publication Activity (10 Years)

Years Active: 1999-2023
Publications (10 Years): 11

Top Topics

Np Hard Problems

Single Instance

Locally Decodable Codes

Combinatorial Search

Top Venues

IACR Cryptol. ePrint Arch.

Publications

Jintai Ding, Vlad Gheorghiu, András Gilyén, Sean Hallgren, Jianqiang Li
Limitations of the Macaulay matrix approach for using the HHL algorithm to solve multivariate polynomial systems. Quantum 7 (2023)
Lior Eldar, Sean Hallgren
An efficient quantum algorithm for lattice problems achieving subexponential approximation factor. CoRR (2022)
Jintai Ding, Vlad Gheorghiu, András Gilyén, Sean Hallgren, Jianqiang Li
Limitations of the Macaulay matrix approach for using the HHL algorithm to solve multivariate polynomial systems. CoRR (2021)
Sean Hallgren, Eunou Lee, Ojas Parekh
An Approximation Algorithm for the MAX-2-Local Hamiltonian Problem. APPROX-RANDOM (2020)
Nai-Hui Chia, Sean Hallgren, Fang Song
On Basing One-way Permutations on NP-hard Problems under Quantum Reductions. Quantum 4 (2020)
Kirsten Eisenträger, Sean Hallgren, Kristin E. Lauter, Travis Morrison, Christophe Petit
Supersingular isogeny graphs and endomorphism rings: reductions and solutions. IACR Cryptol. ePrint Arch. 2018 (2018)
Kirsten Eisenträger, Sean Hallgren, Kristin E. Lauter, Travis Morrison, Christophe Petit
Supersingular Isogeny Graphs and Endomorphism Rings: Reductions and Solutions. EUROCRYPT (3) (2018)
Nai-Hui Chia, Sean Hallgren, Fang Song
On Basing One-way Permutations on NP-hard Problems under Quantum Reductions. CoRR (2018)
Kirsten Eisenträger, Sean Hallgren, Travis Morrison
On the Hardness of Computing Endomorphism Rings of Supersingular Elliptic Curves. IACR Cryptol. ePrint Arch. 2017 (2017)
Nai-Hui Chia, Sean Hallgren
How hard is deciding trivial versus nontrivial in the dihedral coset problem? CoRR (2016)
Nai-Hui Chia, Sean Hallgren
How Hard Is Deciding Trivial Versus Nontrivial in the Dihedral Coset Problem?. TQC (2016)
Sean Hallgren, Adam D. Smith, Fang Song
Classical Cryptographic Protocols in a Quantum World. IACR Cryptol. ePrint Arch. 2015 (2015)
Sean Hallgren, Adam D. Smith, Fang Song
Classical Cryptographic Protocols in a Quantum World. CoRR (2015)
Kirsten Eisenträger, Sean Hallgren, Alexei Y. Kitaev, Fang Song
A quantum algorithm for computing the unit group of an arbitrary degree number field. STOC (2014)
Kirsten Eisenträger, Sean Hallgren, Kristin E. Lauter
Weak Instances of PLWE. Selected Areas in Cryptography (2014)
Kirsten Eisenträger, Sean Hallgren, Kristin E. Lauter
Weak Instances of PLWE. IACR Cryptol. ePrint Arch. 2014 (2014)
Sean Hallgren, Daniel Nagaj, Sandeep Narayanaswami
The local Hamiltonian problem on a line with eight states is QMA-complete. Quantum Inf. Comput. 13 (9-10) (2013)
Sean Hallgren, Adam D. Smith, Fang Song
Classical Cryptographic Protocols in a Quantum World. CRYPTO (2011)
Kirsten Eisenträger, Sean Hallgren
Algorithms for Ray Class Groups and Hilbert Class Fields. SODA (2010)
Sean Hallgren, Cristopher Moore, Martin Rötteler, Alexander Russell, Pranab Sen
Limitations of quantum coset states for graph isomorphism. J. ACM 57 (6) (2010)
Sean Hallgren, Alexandra Kolla, Pranab Sen, Shengyu Zhang
Making Classical Honest Verifier Zero Knowledge Protocols Secure against Quantum Attacks. ICALP (2) (2008)
Sean Hallgren, Aram W. Harrow
Superpolynomial Speedups Based on Almost Any Quantum Circuit. ICALP (1) (2008)
Sean Hallgren
Polynomial-time quantum algorithms for Pell's equation and the principal ideal problem. J. ACM 54 (1) (2007)
Sean Hallgren, Cristopher Moore, Martin Rötteler, Alexander Russell, Pranab Sen
Limitations of quantum coset states for graph isomorphism. STOC (2006)
Wim van Dam, Sean Hallgren, Lawrence Ip
Quantum Algorithms for Some Hidden Shift Problems. SIAM J. Comput. 36 (3) (2006)
Sean Hallgren
Fast quantum algorithms for computing the unit group and class group of a number field. STOC (2005)
Sean Hallgren, Alexander Russell, Igor E. Shparlinski
Quantum Noisy Rational Function Reconstruction. COCOON (2005)
Wim van Dam, Sean Hallgren, Lawrence Ip
Quantum algorithms for some hidden shift problems. SODA (2003)
Sean Hallgren, Alexander Russell, Amnon Ta-Shma
The Hidden Subgroup Problem and Quantum Computation Using Group Representations. SIAM J. Comput. 32 (4) (2003)
Sean Hallgren
Polynomial-time quantum algorithms for Pell's equation and the principal ideal problem. STOC (2002)
Sean Hallgren, Alexander Russell, Amnon Ta-Shma
Normal subgroup reconstruction and quantum computation using group representations. STOC (2000)
Wim van Dam, Sean Hallgren
Efficient Quantum Algorithms for Shifted Quadratic Character Problems CoRR (2000)
Lisa Hales, Sean Hallgren
An Improved Quantum Fourier Transform Algorithm and Applications. FOCS (2000)
Lisa Hales, Sean Hallgren
Quantum Fourier Sampling Simplified. STOC (1999)