BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//CERN//INDICO//EN
BEGIN:VEVENT
SUMMARY:Breaking the Barrier of Self-Concordant Barriers: Faster Interior 
 Point Methods for M-Matrices [Oberseminar Discrete Optimization]
DTSTART:20251201T171500Z
DTEND:20251201T181500Z
DTSTAMP:20260416T080200Z
UID:indico-event-932@math-events.uni-bonn.de
DESCRIPTION:Speakers: Adrian Vladu (CNRS & IRIF\, Université Paris Cité)
 \n\nWe study two fundamental problems in optimization: (1) scaling a symme
 tric positive definite matrix by a positive diagonal matrix so that the re
 sulting matrix has row and column sums equal to 1\, and (2) minimizing a q
 uadratic function subject to hard non-negativity constraints. Both problem
 s lend themselves to efficient algorithms based on interior point methods 
 (IPMs). For general instances\, standard self-concordance theory limits th
 e iteration complexity of IPMs to $\\widetilde{O}(n^{1/2})$\, where $n$ is
  the matrix dimension. We show via an amortized analysis that\, when the i
 nput matrix is an M-matrix\, an IPM with adaptive step sizes solves both p
 roblems in only $\\widetilde{O}(n^{1/3})$ iterations. As a corollary\, usi
 ng fast Laplacian solvers\, we obtain an $\\ell_{2}$ flow diffusion algori
 thm with depth $\\widetilde{O}(n^{1/3})$ and work $\\widetilde{O}(n^{1/3}\
 \cdot \\mathrm{nnz})$. This marks a significant instance where a standard 
 log-barrier IPM permits provably fewer than $O(n^{1/2})$ iterations.\n \n
 The Oberseminar takes place in the Seminarraum\, 1st floor. Participants a
 re invited to have coffee or tea in the lounge before.\n\nhttps://math-eve
 nts.uni-bonn.de/event/932/
LOCATION:Arithmeum\, Lennéstr.\,  2 - Seminarraum (Arithmeum / Research I
 nstitute for Discrete Mathematics)
URL:https://math-events.uni-bonn.de/event/932/
END:VEVENT
END:VCALENDAR