Optimization and Complexity Group, IDSIA
We are the Optimization and Complexity (OC) group, a research group dedicated to bridging the gap between classic optimization problems and complexity theory.
Our team is led by Principal Investigator Monaldo Mastrolilli, alongside Luca Gambardella, who supervises a dynamic group of PhD students and PostDocs.
We are affiliated with the Istituto Dalle Molle di Studi sull’Intelligenza Artificiale (IDSIA), part of both Università della Svizzera Italiana (USI) and Scuola Universitaria Professionale della Svizzera Italiana (SUPSI). Our research hub is located in the charming city of Lugano, Switzerland.
Research Topics
SOS Group
Bit complexity analysis for Sum-of-Squares optimization
Analysis of the computational complexity of the Ideal Membership Problem for instances arising from Constraint Satisfaction Problems
Algebraic proof complexity theory applied to polynomial optimization
Sum-of-Squares approximation hierarchies for Copositive Programming
GAP Group
Theoretical study of exponential but efficient in practice algorithms
Analysis of the integrality gap of combinatorial optimization problems via polyhedral studies
Computational complexity of finding hard instances for heuristics and approximation algorithms
Study of corner / worst case instances for NP-Hard optimization problems
Latest News
Paper accepted at IPCO 2026
Our paper “The Integrality Gap of the Traveling Salesman Problem is 4/3 if the LP Solution Has at Most n+6 Non-Zero Components” has been accepted at IPCO 2026.
EUROYoung Workshop 2026 in Lugano
The OC Group and the Intelligent System Group at IDSIA will host the EUROYoung Workshop 2026!
Paper accepted on Discrete Optimization
Our paper “On the Integrality Gap of Small Asymmetric Travelling Salesman Problems: A Polyhedral and Computational Approach” has been accepted at the journal Discrete Optimization.