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]


    Up [ Return to home page ]