Convex relaxations [1] (such as linear programming relaxation) have been widely studied in theoretical computer science [2, 3] and operational research, and have been successfully applied to various fields of artificial intelligence, such as local clustering, segmentation, and three-dimensional reconstruction. Their quantum implementations on specific NP-hard problems [4] have shown to provide better approximations compared to classical counterparts. The proposed theses can either focus on the study and review of the literature on the subject (compilative theses), or on the development and analysis of new algorithms for combinatorial problems on graphs or other structures, based on quantum or hybrid computational models (classical-quantum), with the goal of achieving improved computational efficiency. Basic knowledge of linear algebra, algorithms and data structures is strongly recommended.
[1] S. P. Boyd and L. Vandenberghe. Convex Optimization. Cambridge University Press, 2004.
[2] M. Bodirsky, M. Mamino, and C. Viola. Piecewise Linear Valued CSPs Solvable by Linear Programming Relaxation. ACM Trans. Comput. Logic, 23(1), nov 2021.
[3] C. Viola and S. Živný. The Combined Basic LP and Affine IP Relaxation for Promise VCSPs on Infinite Domains. ACM Trans. Algorithms, 17(3), july 2021.
[4] D.J. Egger. et al. Warm-starting quantum optimization. Quantum, 2020.