TUM – TUM – Menü
Lattice Problems: Theory and Algorithms
seminar

Advisors: Prof. Dr. P. Gritzmann, Dipl.-Math V. Ghiglione
ECTS credits: 3
Time and Room: Thu. 14.15--15.45, Room 02.04.011

News

  • 16th Mar. 2016: The Seminar schedule has been modified to a newer version, see below.
  • 22nd Feb. 2016: The topics are finalized and assigned to lecturers.
  • 5th Feb. 2016: Presentation meeting, room 02.06.020 at 14:00.

Topics

  • Diophantine Approximation
  • Lattice Theory and Lattice Problems
  • Successive Minima, Minkowski's Theorems
  • Gauss and LLL-reduction
  • Solutions of Lattice Problems through reduction
  • Counting Lattice Points in Polyhedra
  • Applications to Code Theory and Algebra

Prerequisites

  • Algorithmische Diskrete Mathematik (MA2501)
  • Propädeutikum Diskrete Mathematik (MA1501, MA1503)
  • Fundamentals of Convex Optimization (MA2504)

Talks and Schedule

Date Lecturer Topic
21.04.16 All A 5-minute overview of your topic
12.05.16 Anna Surner Fundamentals of Lattice Theory
02.06.16 Andreas Stephan Basis Reduction and Lattice Problems
09.06.16 Martin Bullinger Minkowski's Theorems and Applications
23.06.16 Lorenz Panny LLL-Reduction and Applications
30.06.16 Roman Karim Gilg Lattices in Cryptography
14.07.16 Andreas Josef Kohl Lattice Points in Polyhedra

Topics description, as well as suggested literature, can be found here.

Please fix a meeting 2-3 weeks before your talk, to discuss the outline and the media that you will use.

Literature

Books form Springer-Verlag can be downloaded with your TUM credentials at http://link.springer.com/ logging in "via Shibboleth". If you have troubles finding the other books, please contact Viviana Ghiglione.

  • [1] M. Beck and S. Robins. Computing the Continuous Discretely: Integer-point Enumeration in Polyhedra. Undergraduate Texts in Mathematics. Springer New York, 2007.
  • [2] J.W.S. Cassels. An introduction to the geometry of numbers. Grundlehren der mathematischen Wissenschaften. Springer, 1959.
  • [3] C.P. Schnorr, R. Fischlin. Gittertheorie und algorithmische geometrie, reduktion von gitterbasen und polynomidealen. Goethe-Universitt Frankfurt/Main http://www.math.uni-frankfurt.de/ismi/schnorr/lecturenotes/gitter.pdf, 1994. pdf
  • [4] P. Erdös, P.M. Gruber, and J. Hammer. Lattice points. Pitman monographs and surveys in pure and applied mathematics. Longman Scientific & Technical, 1989.
  • [5] Steven D. Galbraith. Mathematics of Public Key Cryptography. Cambridge University Press, New York, NY, USA, 1st edition, 2012. pdf
  • [6] Oded Goldreich, Shafi Goldwasser, and Shai Halevi. Public-key cryptosystems from lattice reduction problems. In Proceedings of the 17th Annual International Cryptology Conference on Advances in Cryptology, CRYPTO ’97, pages 112–131, London, UK, UK, 1997. Springer-Verlag. pdf
  • [7] P. Gritzmann. Grundlagen der Mathematischen Optimierung: Diskrete Strukturen, Komplexitätstheorie, Konvexitätstheorie, Lineare Optimierung, Simplex-Algorithmus, Dualität. Aufbaukurs Mathematik. Springer Fachmedien Wiesbaden, 2013.
  • [8] Martin Henk, Achill Schrmann, and Jrg M. Wills. Ehrhart polynomials and successive minima. Mathematika, 52:1–16, 2005. pdf
  • [9] A. Leutbecher. Zahlentheorie: Eine Einführung in die Algebra. Grundwissen Mathematik. Springer Berlin Heidelberg, 1996.
  • [10] Jiri Matousek. Lectures on Discrete Geometry. Springer-Verlag New York, Inc., Secaucus, NJ, USA, 2002.
  • [11] Phong Q. Nguyen and Jacques Stern. The two faces of lattices in cryptology. In Revised Papers from the International Conference on Cryptography and Lattices, CaLC’01, pages 146–180, London, UK, UK, 2001. Springer-Verlag https://cr.yp.to/bib/2001/nguyen.ps. pdf
  • [12] Alexander Schrijver. Theory of Linear and Integer Programming. John Wiley & Sons, Inc., New York, NY, USA, 1986.
  • [13] C.D. Toth, J. O’Rourke, and J.E. Goodman. Handbook of Discrete and Computational Geometry, Second Edition. Discrete and Combinatorial Mathematics Series. CRC Press, 2004. pdf

Research Unit M9


Department of Mathematics
Boltzmannstraße 3
85748 Garching b. München
Germany
phone:+49 89 289-16858
fax:+49 089 289-16859
sekretariat-m9ma.tum.de

Professors

Prof. Dr. Peter Gritzmann
Applied Geometry and Discrete Mathematics

Prof. Dr. Andreas S. Schulz
Mathematics of Operations Research
(affiliated member of M9)

Prof. Dr. Stefan Weltge
Discrete Mathematics

News

April 2018
Case Studies 2018: Save the date: Case Studies poster presentation on May 25th, 2018, final workshop on July 7th, 2018.