Jeffrey C. Lagarias: Papers on Algorithms/ Computational Complexity

• Succinct Certificates for the Solvability of Binary Quadratic Diophantine Equations ,
  J. C. Lagarias,
  Proc. 20th IEEE Symposium on Foundations of Computer Science , IEEE Press 1979, pp. 47-54.

• Worst-case complexity bounds in the theory of integral quadratic forms ,
  J. C. Lagarias,
  J. Algorithms 1 (1980), pp. 142-186.

• On the computational complexity of determining the solvability or unsolvability of the equation X^2 - dY^2 = -1 ,
  J. C. Lagarias,
  Trans. Amer. Math. Soc. 260 (1980), pp. 485-508.

• New algorithms for computing pi(x),
  J. C. Lagarias and A. M. Odlyzko,
  pp. 176-193 in Number Theory: New York 1982,
  (D. V. Chudnovsky, G. V. Chudnovsky, H. Cohn and M. B. Nathanson,eds.),
  Springer-Verlag, Lecture Notes in Mathematics #1052, 1984.

• The computational complexity of simultaneous Diophantine approximation problems ,
  J. C. Lagarias,
  SIAM J. Computing 14 (1985), pp. 196-209.
  [Preliminary version in: Proc 23rd Annual Symposium on Foundations of Computer Science, IEEE Press 1982, pp. 32-39.]

• Solving low-density subset sum problems,
  J. C. Lagarias and A. M. Odlyzko,
  J. ACM, 32 (1985), pp. 229-246.
  [Preliminary version in Proc. 24th Annual Symposium on Foundations Computer Science ,IEEE Press 1983, pp. 1-10.]

• Computing pi(x): An analytic method,
  J. C. Lagarias and A. M. Odlyzko,
  J. Algorithms, 8 (1987), pp. 173-191. [PostScript]

• Polynomial time algorithms for finding integer relations among real numbers ,
  J. Hastad, B. Just, J. C. Lagarias and C. P. Schnorr,
  SIAM J. Computing 18 (1989), pp. 859-881.
  [Preliminary version in: STACS '86 , Lecture Notes in Computer Science No. 210, Springer-Verlag: New York 1986, pp. 105-118.]

• One-way functions and circuit complexity ,
  R. Boppana and J. C. Lagarias,
  Information and Computation 74 (1987), pp. 226-240.
  [Preliminary version in: Structure in Complexity Theory ,
  Lecture Notes in Computer Science No. 223, Springer-Verlag: New York 1986, pp. 51-65.]

• Algorithms for square packing: A probabilistic analysis ,
  E. G. Coffman, Jr. and J. C. Lagarias,
  SIAM J. Computing (1989), pp. 166-185.

• Probabilistic Algorithms for Speedup ,
  Joan Feigenbaum and Jeffrey C. Lagarias,
  Statistical Science 8 (1993), pp. 20-25.

• Geodesic Multidimensional Continued Fractions ,
  J. C. Lagarias,
  Proc. London Math. Soc. 69 (1994), pp. 464-488.

• The d-Step Conjecture and Gaussian Elimination ,
  J. C. Lagarias, N. Prabhu, and J. A. Reeds,
  Discrete & Computational Geometry , 18 (1997), pp. 53-82. [PostScript]

• The Computational Complexity of Knot and Link Problems
  Joel Hass, Jeffrey C. Lagarias and Nick Pippenger,
  J. A. C. M. 46 (1999), 185--211. [PostScript]

• The number of Reidemeister moves needed for unknotting ,
  Joel Hass and Jeffrey C. Lagarias,
  J. Amer. Math. Soc., 14 (2001), 399--428. [PostScript]