Finding a largest clique in a network belongs to the celebrated list of 21 computationally hard problems, established by Richard Karp in 1972. Cliques model interconnections in networks, just like their close relatives: independent sets. They are useful, for instance, to investigate mutual friendships in social networks, predict protein structures in bioinformatics, or find best allocations in logistics. Luis Felipe Vargas (CWI) and his colleagues discovered novel structural properties of approximation bounds for these hard graph parameters, answering some long standing open questions. Vargas defended his PhD thesis ‘Sum-of-Squares Representations for Copositive Matrices and Independent Sets in Graphs’ at Tilburg University with honours (cum laude) on 3 November 2023.
Cum laude for Luis Felipe Vargas for research in optimization
Mathematician Luis Felipe Vargas (CWI) received a 'cum laude' degree for his thesis on optimization. His PhD research resulted in a new mathematical insight on approximation bounds for graph parameters.
Luis Felipe Vargas explains his research to fellow mathematicians: “Computing the size of the largest clique can be formulated as linear optimization over the cone of copositive matrices, thereby lifting the usual problem formulation from vectors to well-structured matrices with a high modelling power. In 2000, Parrilo introduced approximation hierarchies for this cone, based on the algebraic notion of sums of squares of polynomials, and, in 2002, de Klerk and Pasechnik used them to design tractable bounds for the maximum clique parameter. In my research, I have unraveled structural properties of these hierarchies. Together with colleagues, I have shown that these bounds recover the clique parameter exactly. For this, we show that certain graph polynomials enjoy several properties related with sums of squares. This result offers the first substantial progress in twenty years on an open question by de Klerk and Pasechnik. In addition, I characterized the matrix sizes for which the hierarchies suffice to capture the full copositive cone. In my work the interplay between algebra and optimization is two-ways: we use algebraic techniques as powerful toolbox for designing tractable approximations for optimization problems, but we also give novel contributions about sums of squares representations of positive polynomials. My results have also somewhat surprising complexity implications: Deciding whether a polynomial has finitely many minimizers in a simplex region is NP-hard, while this question restricted to linear functions has a polynomial-time algorithm.”
About Luis Felipe Vargas
Luis Felipe Vargas did his research in the Network & Optimization group of the Centrum Wiskunde & Informatica (CWI) in Amsterdam, the Netherlands. He previously studied mathematics at Universidad de Los Andes in Bogota, after receiving several distinctions at (inter)national Mathematics Olympiads. His research was supported by the EU Consortium POEMA, within the Marie Skłodowska-Curie Actions — Innovative Training Networks funding scheme. Vargas received a best poster award at the IPCO 2021 conference, and he was selected as one of the four nominees for the KWG Prize at the Dutch Congress of Mathematics (NMC) in 2023. After his PhD defence, he takes a postdoctoral position at IDSIA in Lugano from mid-November.
- PhD thesis: Sum-of-Squares Representations for Copositive Matrices and Independent Sets in Graphs
- Promotor: Monique Laurent (CWI, Tilburg Unversity), co-promotor: Juan Vera Lizcano (Tilburg University)
- Personal homepage of Luis Felipe Vargas