Séminaire de Maths-Info

Mini cours: Optimization, lattices, spherical designs (1/2)

by Frank Vallentin (Collogne)

Europe/Paris
Salle Pellos (1R2 - 207) le mercredi et Salle Cavailles (1R2 - 132) le jeudi

Salle Pellos (1R2 - 207) le mercredi et Salle Cavailles (1R2 - 132) le jeudi

Description

Lattices (discrete subgroups of n-dimensional Euclidean spaces) are ubiquitous objects in mathematics.

One typical class of lattice problems is finding a good lattice with respect to some parameter, for instance minimizing packing density, maximizing covering density, minimizing potential energy, minimizing the quantization constant. When locally looking at these optimization problems the concept of spherical designs (finite point sets on the sphere which provide excellent cubature formulas for polynomials) often plays a central role. I will look at this phenomenon in depth.

Another typical problem for lattices is algorithmic. For instance the closest vector problem (given a lattice and a point in Euclidean space, what is the closest lattice vector to this given point?). In general the closest vector problem is NP-hard. I will show that one can solve the closest vector problem in polynomial time for special classes of lattices.

One new approach to efficiently solve the closest vector problem for other classes of lattices could go via the concept of least distortion metric embeddings: How to embed the flat torus given by a lattice into Euclidean space with minimal metric distortion. I will show how a semidefinite optimization approach can be used to find and analyze least distortion Euclidean embeddings of flat tori.


Quand et où :

- Mercredi 08 Février : 10h-12h, Salle Pellos (1R2 - 207)
- Jeudi 09 Février : 10h-12h, Salle Cavailles (1R2 - 132)
 

From the same series
2