Public talk within a professorship procedure of Stanislav Živný, Doctor of Philosophy (University of Oxford)
On behalf of the chairman of the evaluation committee, Prof. Kučera, we would like to invite you to the public talk within a professorship procedure of Prof. Stanislav Živný (University of Oxford).
Title of the lecture: Power of convex relaxations in discrete optimisation
Abstract: Which discrete optimisation problems can be solved efficiently and why? My research is concerned with designing efficient algorithms and finding the exact borderline of tractability. For a broad class of computational problems, known as constraint satisfaction problems (CSPs), we now have a good understanding of this fundamental question. In this talk I'll survey my work on the power of convex relaxations for constraint satisfaction problems.