Algorithmics and Lattices

Lattice Algorithms 投影片期刊整理 last update: 25/01/2007 13:47

LLL Algorithm, Small Dimension, Integer programming, CVP, Randomized, Parallel Algorithms, other, 相關網頁, 回首頁

The LLL Algorithm and its variations:

[LLL82] A. Lenstra, H. Lenstra, L. Lov脃sz, "Factoring Polynomials with Rational Coefficients," Math. Ann. , Vol. 261, 1982.
[Schnorr87] C. P. Schnorr, "A Hierarchy of Polynomial Time Lattice Basis Reduction," Theoretical Computer Science, Vol. 53, 1987.
[Pohst87] M. Pohst, "A Modification of the LLL Reduction Algorithm," JSC , Vol. 4, 1987.
[Schnorr88] C. P. Schnorr, "A more Efficient Algorithm for Lattice Basis Reduction," Journal of Algorithms, Vol. 9, 1988. [投影片]
[LLS90] J. Lagarias, H. Lenstra, C. P. Schnorr, "Korkine-Zolotarev Bases and Successive Minima of a Lattice and its Reciprocal Lattice," Combinatorica, Vol. 10, 1990.
[LS92] L. Lov脃sz, H. Scarf, "The generalized basis reduction algorithm," Mathematics of Operations Research, Vol 17, 1992.
[Schnorr94] C. P. Schnorr, "Block Reduced Lattice Bases and Successive Minima," Combinatorics, Probability and Computing, Vol. 3, pp. 507-522, 1994.
[ES94] M. Euchner, C. P. Schnorr, "Lattice Basis Reduction: Improved Practical Algorithms and Solving Subset Sum Problems," Computer Science and Mathematics and Statistics, Vol. 66(1-3), pp. 181-199, 1994.
[DV94] H. Daude, B. Vallee, "An upper bound on the average number of iterations of the LLL algorithm," Theoretical Computer Science, VOL. 123(1), pp. 95-115, 1994.
[RS95] C. R螌ssner, C. P. Schnorr, "Computation of Highly Regular Nearby Points," Theory of Computing and Systems, 1995.
[RS96] C. R螌ssner,C. P. Schnorr, "An Optimal, Stable Continued Fraction Algorithm for Arbitrary Dimension," fifth-IPCO, Lecture Notes in Computer Science, Vol. 1084, 1996.
[FP96] C. Fieker, M. Pohst, "On Lattices over Number Fields," ANTS II, Lecture Notes in Computer Science, Vol. 1122, pp. 133-140, 1996
[Ajtai96] M. Ajtai, "Generating hard instances of lattice problems," ACM Symposium on Theory of Computing, pp. 99-108, 1996.
[PS96] M. Pohst, M. Schornig, "On Integral Basis Reduction in Global Function Fields," Lecture Notes In Computer Science, Vol. 1122, pp. 273-282, 1996.
[RR97] H. Ritter, C. Rossner, "Factoring via Strong Lattice Reduction Algorithms," http://www.mi.informatik.uni-frankfurt.de/, 1997.
[Paulus98] S. Paulus, "Lattice Basis Reduction in Function Fields," Proceedings of the Third Symposium on Algorithmic Number Theory, Lecture Notes in Computer Science, Vol. 1423, pp. 567-575, 1998.
[HT98] C. Heckler, L. Thiele, "Complexity Analysis of a Parallel Lattice Basis Reduction Algorithm," SIAM Journal on Computing, Vol. 27(5), pp. 1295-1302, 1998.
[Ajtai98] M. Ajtai, "The shortest vector problem in L2 is NP-hard for randomized reductions (extended abstract)," ACM Symposium on Theory of Computing, pp. 10-19, 1998.
[Akhavi99] A. Akhavi, "Threshold Phenomena in Random Lattices and Efficient Reduction Algorithms," Proceedings of the 7th Annual European Symposium on Algorithms, Lecture Notes In Computer Science, Vol. 1643, pp.476-489, 1999.
[BS99] J. Blomer, J. P. Seifert , "On the complexity of computing short linearly independent vectors and short bases in a lattice," ACM Symposium on Theory of Computing, pp. 711-720, 1999.
[Akhavi00] A. Akhavi, "Worst-case Complexity of the Optimal LLL Algorithm," Lecture Notes in Computer Science, Vol. 1776, 2000.
[KS01-1] H. Koy, C. P. Schnorr, "Segment LLL-Reduction of Lattice Bases," Cryptography and Lattices Conference (CaLC), 2001.
[KS01-2] H. Koy, C. P. Schnorr, "Segment LLL-Reduction with Floating Point Orthogonalization," Lecture Notes in Computer Science, Vol. 2146, 2001.
[Schnorr01] C. P. Schnorr, "New Practical Algorithms For The Approximate Shortest Lattice Vector," http://www.mi.informatik.uni-frankfurt.de/, 2001.
[Micciancio01] D. Micciancio, "The shortest vector in a Lattice is Hard to approximate to within some constant," SIAM Journal on Computing, Vol. 30(6), pp. 2008-2035, 2001.
[KS02] H. Koy, C. P. Schnorr, "Segment and Strong Segment LLL-Reduction of Lattice Bases," Preprint University Frankfurt, 2002.
[Ajtai03] A. Ajtai, "The worst-case behavior of schnorr's algorithm approximating the shortest nonzero vector in a lattice," Proceedings of the thirty-fifth annual ACM symposium on Theory of computing, 2003.
[Schnorr04] C. P. Schnorr, "Fast LLL-Type Lattice Reduction," Information and Computation, Vol. 204(1), pp. 1-25, 2004.
[NS05] P. Q. Nguyen, D. Stehle, "Floating-point LLL revisited," Lecture Notes In Computer Science, Vol. 3494, pp. 215-233, 2005.
[Khot05] S. Khot, "Hardness of Approximating the Shortest Vector Problem in Lattices," Journal of the ACM , Vol. 52(5), pp. 789-808, 2005.

Integer programming

[Lagarias80] J. C. Lagarias, "Worst-Case Complexity Bounds for Algorithms in the Theory of Integral Quadratic Forms," Journal of Algorithms, Vol 1, pp.140-186, 1980.
[Kannan80] R. Kannan, "A Polynomial Algorithm for the Two-Variable Integer Programming Problem," Journal of the ACM, Vol. 27(1), pp. 118-122, 1980.
[Kannan83] R Kannan, "Improved Algorithms for Integer Programming and Related Lattice Problems," ACM, 1983.
[Feit84] S. D. Feit, "A Fast Algorithm for the Two-Variable Integer Programming Problem," Journal of the ACM, Vol. 31(1), pp. 99-113, 1984.
[Sch螌nhage91] A. Sch螌nhage, "Fast Reduction and Composition of Binary Quadratic Forms," Proceedings of the 1991 international symposium on Symbolic and algebraic computation, International Conference on Symbolic and Algebraic Computation, 1991. [投影片]
[Clarkson95] K. L. Clarkson, "Las Vegas algorithms for linear and integer programming when the dimension is small," Journal of the ACM, Vol. 42(2), pp. 488-499, 1995.
[ER01] F. Eisenbrand, G. Rote, "Fast 2 Variable Integer Programming," Integer Programming and Combinatorial Optimization, IPCO'01 of Lecture Notes In Computer Science, Vol. 2081, pp.78-89, 2001.
[ER01_2] F. Eisenbrand, G. Rote, "Fast Reduction of Ternary Quadratic Forms," Lecture Notes In Computer Science, 2001.

Small Dimension Algorithms:

分類表(技術+問題) 關連圖(time) 摘要目標及進度

[Gauss 1801] C. F. Gauss, "Disquisitiones Arithmeticae," Leipzig, 1801
[CC76] B. F. Caviness, G. E. Collins, "Algorithms for Gaussian integer arithmetic," Proceedings of the third ACM symposium on Symbolic and algebraic computation 76, pp. 36-45, 1976.
[Kaltofen83] E. Kaltofen, "On the complexity of finding short vectors in integer lattices," Proceedings of the European Computer Algebra Conference on Computer Algebra,Lecture Notes In Computer Science, Vol. 162, pp.236-244, 1983.
[Kannan85] R. Kannan, "Lattices, basis reduction, and the shortest vector problem," Theory of Algorithms, Colloquia Mathematica Societatis Janos Bolyai, Vol 44, pp. 283-311, 1985.
[Vall眤e87] B. Vall眤e, "An Affine Point of View on Minima Finding in Integer Lattices of Lower Dimensions," Proceedings of the European Computer Algebra Conference on Computer Algebra, Lecture Notes In Computer Science, Vol. 378, pp. 376-378, 1987.
[VF90] B. Vallee, P. Flajolet, "The lattice reduction algorithm of Gauss: an average case analysis," Proceedings of 31st IEEE Symposium on Foundations of Computer Science, Vol. 2, pp. 830-839, 1990.
[Vall眤e91] B. Vall眤e, "Gauss' Algorithm Revisited," Journal of Algorithms, Vol. 12, pp. 556-572, 1991. [投影片]
[Kaib91] M. Kaib, "The Gau憜 Lattice Basis Reduction Algorithm Succeeds With Any Norm," Lecture Notes In Computer Science, Vol. 529 , pp. 275-286,1991
[Yap92] C. K. Yap, "Fast Unimodular Reduction: Planar Integer Lattices," IEEE Symposium on Foundations of Computer Science , 1992.
[KS92] M. Kaib, C. P. Schnorr, "A sharp worst-case analysis of the Gaussian lattice basis reduction algorithm for any norm," Journal of Algorithms, 1992.
[Kaib94] M. Kaib, "A Fast Variant of the Gaussian Reduction Algorithm," Lecture Notes In Computer Science, 1994.
[LP94] M. Lempel, A. Paz,"An algorithm for finding a shortest vector in a two-dimensional modular lattice," Theoretical Computer Science, Vol 125(2), pp. 229-241, 1994. [投影片]
[DFV94] H. Daud眤, P. Flajolet, B. Vall眤e, "An analysis of the Gaussian algorithm for lattice reduction," Lecture Notes In Computer Science, Vol. 877, pp. 144-158, 1994.
[KS96] M. Kaib, C. P. Schnorr, "The Generalized Gauss Reduction Algorithm," Journal of Algorithms, 1996.
[DFV97] H. Daud眤, P. Flajolet, B. Vall眤e, "An Average-case Analysis of the Gaussian Algorithm for Lattice Reduction," Combinatorics, Probability and Computing, 1997. [投影片]
[Rote97] G. Rote, "Finding a Shortest Vector in a Two-Dimensional Lattice Modulo m," Theoretical Computer Science, Vol. 172(1-2), pp. 303-308, 1997.[投影片]
[Semaev01] I. Semaev, "A 3-Dimensional Lattice Reduction Algorithm," Lecture Notes In Computer Science, Vol. 2146, pp. 181-193, 2001.
[Eisenbrand01] F. Eisenbrand, "Short Vectors of Planar Lattices via Continued Fractions," Information Processing Letters, Vol. 79, pp. 121-126, 2001. [投影片]
[NS04] P. Nguyen, D. Stehl眤, "Low-Dimensional Lattice Basis Reduction Revisited (Extended Abstract)," Algorithmic Number Theory: 6th of Lecture Notes In Computer Science, Vol. 3076, pp. 338-357, 2004.
[AS04] A. Akhavi, C. M. D. Santos, "Another View of the Gaussian Algorithm," Theoretical Informatics:6th, Vol. 2976, pp. 474-487, 2004.

Deterministic Algorithms for CVP:

[Kannan83] R. Kannan, "Improved Algorithms for Integer Programming and Related Lattice Problems,"ACM Symposium on Theory of Computing, pp. 93-206, 1983
[Babai85] L. Babai, "On Lov脃sz' Lattice Reduction and the Nearest Lattice Point Problem," Combinatorica : an International Journal of the Janos Bolyai Mathematical Society, Vol 6(1), pp. 1-13, 1985.
[Bl螌mer00] J. Bl螌mer, "Closest Vectors, Successive Minima, and Dual HKZ-bases of Lattices," Lecture Notes In Computer Science, Vol. 1853, 2000.
[Klein00] P. Klein, "Finding the Closest Lattice Vector when it's Unusually Close," ACM-SIAM Symp. Discrete Algorithms, pp. 937-941, 2000.
[AEVZ02] E. Agrell, T. Eriksson, A. Vardy, K. Zeger, "Closest Point Search in Lattices," IEEE Transactions on Information Theory, Vol. 48(8), 2002.

Randomized Algorithms:

[KV97] R. Kannan, S. Vempala, "Sampling Lattice Points," ACM Symposium on Theory of Computing, pp. 696-700, 1997.
[KS01] R. Kumar, D. Sivakumar, "On Polynomial Approximation to the Shortest Lattice Vector Length," Symposium on Discrete Algorithms, pp.126-127, 2001.
[AKS01] M. Ajtai, R. Kumar, D. Sivakumar, "A Sieve Algorithm for the Shortest Lattice Vector Problem," ACM Symposium on Theory of Computing, pp. 601-610, 2001.
[AKS02] M. Ajtai, R. Kumar, D. Sivakumar, "Sampling Short Lattice Vectors and the Closest Lattice Vector Problem," IEEE Annual Conference on Computational Complexity , 2002.
[Schnorr02] C. P. Schnorr, "Lattice Reduction by Random Sampling and Birthday Methods," Lecture Notes In Computer Science, Vol. 2607, 2002.

Parallel Algorithms:

[Villard92] G. Villard, "Parallel Lattice Basis Reduction," ACM Symposium on Theory of Computing, pp. 269 - 277, 1992.
[HT93] C. Heckler, L. Thiele, "Parallel Complexity of Lattice Basis Reduction and a Floating-Point Parallel Algorithm," Lecture Notes In Computer Science, Vol. 694, pp. 744, 1993.
[Ht98] C. Heckler, L. Thiele, "Complexity Analysis of a Parallel Lattice Basis Reduction Algorithm," SIAM Journal on Computing., 1998.
[Wetzel98] S. Wetzel, "An Efficient Parallel Block-Reduction Algorithm," Lecture Notes In Computer Science, Vol. 1423, 1998.

Some other articles:

[KB79] R. Kannan, A. Bachem, "Polynomial Algorithms for Computing of the Smith and Hermite Normal Forms of an Integer Matrix," SIAM Journal of Computing, Vol. 8, 1979.
[Helfrich85] B. Helfrich, "Algorithms to Construct Minkowski Reduced an Hermite Reduced Lattice Bases," Theoretical Computer Science, Vol. 4(2-3), pp. 125-139, 1985.
[BP87] J. Buchmann, M. Pohst, "Computing a Lattice Basis from a System of Generating Vectors," Lecture Notes In Computer Science, Vol. 378, pp. 54-63, 1987.
[Semaev98] I. Semaev, "Evaluation of Linear Relations between Vectors of a Lattice in Euclidean Space," Lecture Notes In Computer Science, Vol. 1423, 1998.
[MW01] D. Micciancio, B. Warinschi, "A Linear Space Algorithm for Computing the Hermite Normal Form," ACM Symposium on Theory of Computing, 2001.
[Regev03] O. Regev, "A Lattice Problem in Quantum NP," IEEE Symposium on Foundations of Computer Science , 2003.