Mediaspace scheduled maintenance: Aug 25, 2026 07:00 - 12:00 AM. During this time, videos will be temporarily unavailable. Check status updates.

Lecture

Closest Vector Problem: Voronoi Cells

In course

MATH-504: Integer optimisation

The course aims to introduce the basic concepts and results of integer optimization with special emphasis on algorithmic problems on lattices that have proved to be important in theoretical computer science and cryptography during the past 30 years. ...

Description

This lecture covers the closest vector problem in lattices, focusing on finding the lattice vector closest to a given target. The instructor explains the concept of Voronoi cells, which partition the space and help determine the closest vector. By defining Voronoi cells as a polytope and exploring the minimal set of inequalities needed to describe them, the lecture delves into the geometric and linear programming aspects of the problem. The discussion includes insights on facet defining inequalities, the uniqueness of minimal inequality sets, and the finite number of relevant vectors in Voronoi cells.

This video is available exclusively on Mediaspace for a restricted audience. Please log in to MediaSpace to access it if you have the necessary permissions.

Watch on Mediaspace

Official source

Related concepts (15)

Polytope

In elementary geometry, a polytope is a geometric object with flat sides (faces). Polytopes are the generalization of three-dimensional polyhedra to any number of dimensions. Polytopes may exist in any general number of dimensions n as an n-dimensional polytope or n-polytope. For example, a two-dimensional polygon is a 2-polytope and a three-dimensional polyhedron is a 3-polytope. In this context, "flat sides" means that the sides of a (k + 1)-polytope consist of k-polytopes that may have (k – 1)-polytopes in common.

Abstract polytope

In mathematics, an abstract polytope is an algebraic partially ordered set which captures the dyadic property of a traditional polytope without specifying purely geometric properties such as points and lines. A geometric polytope is said to be a realization of an abstract polytope in some real N-dimensional space, typically Euclidean. This abstract definition allows more general combinatorial structures than traditional definitions of a polytope, thus allowing new objects that have no counterpart in traditional theory.

Linear programming

Linear programming (LP), also called linear optimization, is a method to achieve the best outcome (such as maximum profit or lowest cost) in a mathematical model whose requirements are represented by linear relationships. Linear programming is a special case of mathematical programming (also known as mathematical optimization). More formally, linear programming is a technique for the optimization of a linear objective function, subject to linear equality and linear inequality constraints.

6-polytope

In six-dimensional geometry, a six-dimensional polytope or 6-polytope is a polytope, bounded by 5-polytope facets. A 6-polytope is a closed six-dimensional figure with vertices, edges, faces, cells (3-faces), 4-faces, and 5-faces. A vertex is a point where six or more edges meet. An edge is a line segment where four or more faces meet, and a face is a polygon where three or more cells meet. A cell is a polyhedron. A 4-face is a polychoron, and a 5-face is a 5-polytope.

Regular polytope

In mathematics, a regular polytope is a polytope whose symmetry group acts transitively on its flags, thus giving it the highest degree of symmetry. All its elements or j-faces (for all 0 ≤ j ≤ n, where n is the dimension of the polytope) — cells, faces and so on — are also transitive on the symmetries of the polytope, and are regular polytopes of dimension ≤ n. Regular polytopes are the generalized analog in any number of dimensions of regular polygons (for example, the square or the regular pentagon) and regular polyhedra (for example, the cube).

Related lectures (34)

Hamiltonian dynamics on convex polytopes

Explores Hamiltonian dynamics on convex polytopes, covering symplectic capacities, EHZ capacity, and systolic ratio maximizers.

Geometry of the Lasso

Explores the geometric explanation of why Lasso solutions are sparse and how coefficients change with the regularization parameter.

Linear Programming: Weighted Bipartite Matching

Covers linear programming, weighted bipartite matching, and vertex cover problems in optimization.

Optimization Methods: Theory Discussion

Explores optimization methods, including unconstrained problems, linear programming, and heuristic approaches.

Hedging for LPs