{"id":150,"date":"2026-02-11T08:26:02","date_gmt":"2026-02-11T08:26:02","guid":{"rendered":"https:\/\/almoa.aau.at\/?page_id=66"},"modified":"2026-03-28T19:27:49","modified_gmt":"2026-03-28T18:27:49","slug":"dc-13-optimal-lattice-vector-quantizers","status":"publish","type":"page","link":"https:\/\/almoa.aau.at\/?page_id=150","title":{"rendered":"DC 13 &#8211; Optimal lattice vector quantizers"},"content":{"rendered":"<div class=\"dc-project\">\r\n<p class=\"wp-block-paragraph\"><strong>Project Title:<\/strong> Optimal lattice vector quantizers<br \/><strong>Doctoral Candidate:<\/strong> N.N.<br \/><strong>Host Institution:<\/strong>\u00a0University of Cologne<br \/><strong>Supervisors:<\/strong> <a href=\"https:\/\/www.mi.uni-koeln.de\/opt\/frank-vallentin\/\">Frank Vallentin<\/a>, <a href=\"https:\/\/homepages.cwi.nl\/~dadush\/\">Daniel Dadush<\/a><\/p>\r\n\r\n\r\n\r\n<p class=\"wp-block-paragraph\"><strong>Objectives:<\/strong> Lattices in n-dimensional Euclidean space are fundamental objects in data science as they provide discrete approximations for many problems in signal processing. The quality of the approximation can for example be measured by the lattice quantizer constant, which is the second moment of the lattice&#8217; Voronoi polytope with an appropriate normalisation. Lattices with small lattice quantizer constant have recently found applications in the design of optimal template banks for detecting gravitational waves. The problem of finding an n-dimensional lattice with smallest possible quantizer constant can be cast as matrix valued non-linear optimisation problem over the cone of positive semidefinite matrices: There is a one-to-one correspondence between lattice bases up to orthogonal transformations and positive semidefinite matrices by taking the Gram matrix of the lattice basis. By work of Barnes and Sloane from the 1980s the optimal value is known up to dimension n = 3. Since then, progress on the problem basically stalled. But recent work by Regev and Stephens-Davidovitz on the reverse Minkowski theorem very surprisingly implies that the objective function is differentiable. This is surprising as infinitesimal perturbations of the lattice can dramatically change the combinatorial structure of its Voronoi polytope. The DC will apply and extend this surprising result to find locally optimal lattice quantizers. For solving this optimisation problem an efficient evaluation oracle of the objective, that is the second moment of the Voronoi polytope is needed. The DC will derive this oracle by splitting the integration domain using mixed coherent subdivisions in the spirit of the polyhedral Cayley trick of Sturmfels.<\/p>\r\n\r\n\r\n\r\n<p class=\"wp-block-paragraph\"><strong>Expected Results:<\/strong> The DC will aim to classify all locally optimal lattices up to dimension 5 (only up to this dimension the classification of Voronoi polytopes is known; in dimension 6 this enumeration is no longer tractable). The DC will determine which highly symmetric lattices are locally optimal for lattice quantization. The DC will make progress on the complexity of determining the lattice quantizer constant, for example it is conjectured that one can compute the lattice quantizer constant in polynomial time in the case of zonotopal lattices. In general, the DC will substantially improve our local and global understanding of the \u201cenergy\u201d landscape of lattice quantizers.<\/p>\r\n\r\n\r\n\r\n<p class=\"wp-block-paragraph\"><strong>Planned secondment:<\/strong> 3 months at DLR (M. Epping) in the end of the 1st year to gain experience with optimisation problems in the context of quantum information and quantum computing; 6 months at NWO-I (D. Dadush) during the 2nd year to learn about the reverse Minkowski theorem and about complexity of and algorithms for lattice problems.<\/p>\r\n\r\n\r\n\r\n<p class=\"wp-block-paragraph\"><strong>Degree awarding institution:<\/strong> University of Cologne<\/p>\r\n<\/div>","protected":false},"excerpt":{"rendered":"<p>Project Title: Optimal lattice vector quantizersDoctoral Candidate: N.N.Host Institution:\u00a0University of CologneSupervisors: Frank Vallentin, Daniel Dadush Objectives: Lattices in n-dimensional Euclidean space are fundamental objects in data science as they provide discrete approximations for many problems in signal processing. The quality of the approximation can for example be measured by the [&hellip;]<\/p>\n","protected":false},"author":3,"featured_media":0,"parent":0,"menu_order":0,"comment_status":"closed","ping_status":"closed","template":"","meta":{"_crdt_document":"","footnotes":""},"class_list":["post-150","page","type-page","status-publish","hentry"],"_links":{"self":[{"href":"https:\/\/almoa.aau.at\/index.php?rest_route=\/wp\/v2\/pages\/150","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/almoa.aau.at\/index.php?rest_route=\/wp\/v2\/pages"}],"about":[{"href":"https:\/\/almoa.aau.at\/index.php?rest_route=\/wp\/v2\/types\/page"}],"author":[{"embeddable":true,"href":"https:\/\/almoa.aau.at\/index.php?rest_route=\/wp\/v2\/users\/3"}],"replies":[{"embeddable":true,"href":"https:\/\/almoa.aau.at\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=150"}],"version-history":[{"count":4,"href":"https:\/\/almoa.aau.at\/index.php?rest_route=\/wp\/v2\/pages\/150\/revisions"}],"predecessor-version":[{"id":879,"href":"https:\/\/almoa.aau.at\/index.php?rest_route=\/wp\/v2\/pages\/150\/revisions\/879"}],"wp:attachment":[{"href":"https:\/\/almoa.aau.at\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=150"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}