Professor Standa Živný
Professor in Computer Science; Fellow of Merton College
About
Professor Standa Živný's research is in the broad area of theoretical computer science and discrete mathematics, where his work centres around the application of mathematics to the design and analysis of algorithms and understanding the inherent limits of efficient computation.
In the last few years, he has mostly focused on the mathematics of so-called promise constraint satisfaction problems. These are problems of the following type: Given a 3-colourable graph, is it possible to find a 6-colouring efficiently? Professor Živný’s research investigates when this and similar problems can be solved efficiently, in particular by combinations of convex and linear Diophantine.
Expertise
- Algorithms
- Computational complexity
- Discrete optimisation
- Constraint satisfaction
- Submodular functions
Selected publications
- Algebraic Approach to Approximation (2024)
- Semidefinite Programming and Linear Equations vs. Homomorphism Problems (2024)
- Approximate Graph Colouring and the Hollow Shadow (2023)
- Topology and Adjunction in Promise Constraint Satisfaction (2023)
- Pliability and Approximating Max-CSPs (2023)
- The Complexity of Finite-Valued CSPs (2016)
Languages
English, Czech