Spring 2020

A Simplex-Type Voronoi Algorithm Based on Short Vector Computations of Copositive Quadratic Forms

Friday, Feb. 21, 2020 11:30 am12:00 pm PST

Add to Calendar


Achill Schurmann, University of Rostock


Calvin Lab Auditorium

Voronoi‘s algorithm is classically used to solve the lattice sphere packing problem in a given dimension by enumerating all perfect quadratic forms of a given rank. A key component of the procedure is the computation of shortest vectors. In this talk we propose a simplex-type adaption of Voronoi‘s algorithm allowing to compute rational cp-certificates as used in convex optimization. A key element and currently the main bottleneck in this algorithm is an adapted shortest vector computation, asking for all integer vectors that are short with respect to a given copositive quadratic form.

(Based on joint work with Mathieu Dutour Sikiric and Frank Vallentin)
PDF icon completepositivityberkeley2020.pdf3.69 MB