Sean Hallgren

According to our database, Sean Hallgren authored at least 30 papers between 1999 and 2023.

Collaborative distances:

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

2023

Limitations of the Macaulay matrix approach for using the HHL algorithm to solve multivariate polynomial systems.

Jintai Ding, Vlad Gheorghiu, András Gilyén, Sean Hallgren, Jianqiang Li

Quantum, July, 2023

2022

An efficient quantum algorithm for lattice problems achieving subexponential approximation factor.

Lior Eldar, Sean Hallgren

CoRR, 2022

2020

On Basing One-way Permutations on NP-hard Problems under Quantum Reductions.

Nai-Hui Chia, Sean Hallgren, Fang Song

Quantum, 2020

An Approximation Algorithm for the MAX-2-Local Hamiltonian Problem.

Sean Hallgren, Eunou Lee, Ojas Parekh

Proceedings of the Approximation, 2020

2018

Supersingular isogeny graphs and endomorphism rings: reductions and solutions.

Kirsten Eisenträger, Sean Hallgren, Kristin E. Lauter, Travis Morrison, Christophe Petit

IACR Cryptol. ePrint Arch., 2018

2017

On the Hardness of Computing Endomorphism Rings of Supersingular Elliptic Curves.

Kirsten Eisenträger, Sean Hallgren, Travis Morrison

IACR Cryptol. ePrint Arch., 2017

2016

Quantum Algorithms for Class Group of a Number Field.

Sean Hallgren

Encyclopedia of Algorithms, 2016

Quantum Algorithm for Solving Pell's Equation.

Sean Hallgren

Encyclopedia of Algorithms, 2016

Quantum Algorithm for Factoring.

Sean Hallgren

Encyclopedia of Algorithms, 2016

How Hard Is Deciding Trivial Versus Nontrivial in the Dihedral Coset Problem?.

Nai-Hui Chia, Sean Hallgren

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

2015

Classical Cryptographic Protocols in a Quantum World.

Sean Hallgren, Adam D. Smith, Fang Song

IACR Cryptol. ePrint Arch., 2015

2014

Weak Instances of PLWE.

Kirsten Eisenträger, Sean Hallgren, Kristin E. Lauter

IACR Cryptol. ePrint Arch., 2014

A quantum algorithm for computing the unit group of an arbitrary degree number field.

Kirsten Eisenträger, Sean Hallgren, Alexei Y. Kitaev, Fang Song

Proceedings of the Symposium on Theory of Computing, 2014

2013

The local Hamiltonian problem on a line with eight states is QMA-complete.

Sean Hallgren, Daniel Nagaj, Sandeep Narayanaswami

Quantum Inf. Comput., 2013

2010

Limitations of quantum coset states for graph isomorphism.

Sean Hallgren, Cristopher Moore, Martin Rötteler, Alexander Russell, Pranab Sen

J. ACM, 2010

Algorithms for Ray Class Groups and Hilbert Class Fields.

Kirsten Eisenträger, Sean Hallgren

Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms, 2010

2008

Quantum Algorithms for Class Group of a Number Field.

Sean Hallgren

Proceedings of the Encyclopedia of Algorithms - 2008 Edition, 2008

Quantum Algorithm for Solving the Pell's Equation.

Sean Hallgren

Proceedings of the Encyclopedia of Algorithms - 2008 Edition, 2008

Quantum Algorithm for Factoring.

Sean Hallgren

Proceedings of the Encyclopedia of Algorithms - 2008 Edition, 2008

Making Classical Honest Verifier Zero Knowledge Protocols Secure against Quantum Attacks.

Sean Hallgren, Alexandra Kolla, Pranab Sen, Shengyu Zhang

Proceedings of the Automata, Languages and Programming, 35th International Colloquium, 2008

Superpolynomial Speedups Based on Almost Any Quantum Circuit.

Sean Hallgren, Aram W. Harrow

Proceedings of the Automata, Languages and Programming, 35th International Colloquium, 2008

2007

Polynomial-time quantum algorithms for Pell's equation and the principal ideal problem.

Sean Hallgren

J. ACM, 2007

2006

Quantum Algorithms for Some Hidden Shift Problems.

Wim van Dam, Sean Hallgren, Lawrence Ip

SIAM J. Comput., 2006

2005

Fast quantum algorithms for computing the unit group and class group of a number field.

Sean Hallgren

Proceedings of the 37th Annual ACM Symposium on Theory of Computing, 2005

Quantum Noisy Rational Function Reconstruction.

Sean Hallgren, Alexander Russell, Igor E. Shparlinski

Proceedings of the Computing and Combinatorics, 11th Annual International Conference, 2005

2003

The Hidden Subgroup Problem and Quantum Computation Using Group Representations.

Sean Hallgren, Alexander Russell, Amnon Ta-Shma

SIAM J. Comput., 2003

2000

Efficient Quantum Algorithms for Shifted Quadratic Character Problems

Wim van Dam, Sean Hallgren

CoRR, 2000

Normal subgroup reconstruction and quantum computation using group representations.

Sean Hallgren, Alexander Russell, Amnon Ta-Shma

Proceedings of the Thirty-Second Annual ACM Symposium on Theory of Computing, 2000

An Improved Quantum Fourier Transform Algorithm and Applications.

Lisa Hales, Sean Hallgren

Proceedings of the 41st Annual Symposium on Foundations of Computer Science, 2000

1999

Quantum Fourier Sampling Simplified.

Lisa Hales, Sean Hallgren

Proceedings of the Thirty-First Annual ACM Symposium on Theory of Computing, 1999