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

Lecture

Voronoi Analysis: Closest Vector Problem

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 Voronoi analysis applied to the Closest Vector Problem (CVP), discussing the computation of Voronoi cells and their relevance in solving CVP efficiently. The instructor explains the relationship between lattice reduction and CVP solutions, emphasizing the importance of Voronoi analysis in this context.

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 (32)

Lattice problem

In computer science, lattice problems are a class of optimization problems related to mathematical objects called lattices. The conjectured intractability of such problems is central to the construction of secure lattice-based cryptosystems: Lattice problems are an example of NP-hard problems which have been shown to be average-case hard, providing a test case for the security of cryptographic algorithms. In addition, some lattice problems which are worst-case hard can be used as a basis for extremely secure cryptographic schemes.

Lattice-based cryptography

Lattice-based cryptography is the generic term for constructions of cryptographic primitives that involve lattices, either in the construction itself or in the security proof. Lattice-based constructions are currently important candidates for post-quantum cryptography. Unlike more widely used and known public-key schemes such as the RSA, Diffie-Hellman or elliptic-curve cryptosystems — which could, theoretically, be defeated using Shor's algorithm on a quantum computer — some lattice-based constructions appear to be resistant to attack by both classical and quantum computers.

Time

Time is the continued sequence of existence and events that occurs in an apparently irreversible succession from the past, through the present, into the future. It is a component quantity of various measurements used to sequence events, to compare the duration of events or the intervals between them, and to quantify rates of change of quantities in material reality or in the conscious experience. Time is often referred to as a fourth dimension, along with three spatial dimensions.

Time zone

A time zone is an area which observes a uniform standard time for legal, commercial and social purposes. Time zones tend to follow the boundaries between countries and their subdivisions instead of strictly following longitude, because it is convenient for areas in frequent communication to keep the same time. All time zones are defined as offsets from Coordinated Universal Time (UTC), ranging from UTC−12:00 to UTC+14:00. The offsets are usually a whole number of hours, but a few zones are offset by an additional 30 or 45 minutes, such as in India, South Australia and Nepal.

Time travel

Time travel is the hypothetical activity of traveling into the past or future. Time travel is a widely recognized concept in philosophy and fiction, particularly science fiction. In fiction, time travel is typically achieved through the use of a hypothetical device known as a time machine. The idea of a time machine was popularized by H. G. Wells' 1895 novel The Time Machine. It is uncertain if time travel to the past is physically possible, and such travel, if at all feasible, may give rise to questions of causality.

Related lectures (27)

Numerics: semester project

Covers the semester project on numerics, focusing on adaptive algorithms and multistep methods.

Numerical Analysis: Implicit Schemes

Covers implicit schemes in numerical analysis for solving partial differential equations.

Finite Difference Grids

Explains finite difference grids for computing solutions of elastic membranes using Laplace's equation and numerical methods.

Runge-Kutta Methods

Explains the Runge-Kutta methods, particularly the explicit scheme of order 4 (ERK4), and how to optimize parameters for accuracy.

Multistep methods