Date/Time
Date(s) - 29/06/2023
11:00 am - 12:30 pm
Location
The School of Informatics, University of Edinburgh
SICSA DVF Dr Alexandros Hollender will be giving a talk on ‘The Complexity of Computing KKT Solutions of Quadratic Programmes’ on 29 June 2023 at the University of Edinburgh
Abstract: It is well known that solving a (non-convex) quadratic program is NP-hard. We show that the problem remains hard even if we are only looking for a KKT point, instead of a global optimum. Namely, we prove that computing a KKT point of a quadratic polynomial over the domain [0,1]^n is complete for the class CLS = PPAD ∩ PLS.
Short Bio: Alexandros Hollender is currently a postdoctoral researcher at the École Polytechnique Fédérale de Lausanne (EPFL). Last year, he was a postdoctoral research fellow at All Souls College, University of Oxford. He obtained his PhD from the University of Oxford under the supervision of Paul Goldberg.
His research interests lie mainly in algorithms and computational complexity, including applications in various fields such as game theory, fair division and optimization. His work focuses on total search problems and the various complexity classes that arise in their study. In 2021 he received the best paper award in the ACM Symposium on Theory of Computing (STOC) for his work on the computational complexity of the gradient descent method. In 2022, he received the European Association for Theoretical Computer Science (EATCS) distinguished dissertation award for his doctoral thesis “Structural Results for Total Search Complexity Classes with Applications to Game Theory and Optimisation”
If you would like to attend this talk, please register at https://www.eventbrite.com/e/alexandros-hollender-the-complexity-of-computing-kkt-solutions-of-quadrati-tickets-646320220177
