# Victor Lagerkvist

Associate Professor, Docent

Associate professor with habilitation (universitetslektor and docent) at the theoretical computer science laboratory (TCSLAB).

## Theoretical computer science

I am associate professor with habilitation (universitetslektor and docent) at the theoretical computer science laboratory (TCSLAB).

My main research interest is the so-called algebraic approach for analysing computational complexity. In short, many computational problems can be modelled as problems where the goal is to assign values to variables, subjected to certain constraints (constraint satisfaction problems). In the worst case, one might have to try all possible combinations of domain values to the variables in the instance, which yields an exponential running time (bad!). But it is known that the set of solutions to a constraint satisfaction problem can be described by certain symmetries, called polymorphisms, which makes it possible to reason about the solution space in a non-trivial way. In fact, it is even known that for finite domains, the presence of any non-trivial method to combine solutions, is sufficient for the existence of a polynomial-time algorithm (good!).

However, classical complexity fails to adequately adress why there is such a large difference in complexity even among problems with an expected superpolynomial running time. For example, why does there exist small instances containing only a handful of variables, which makes even the most sophisticated solvers crawl to a halt, when the same solvers manage to handle real-world instances with millions of variables?

To answer such questions the normal algebraic approach is not applicable, since the presence of a non-trivial polymorphism would result in a polynomial time solvable problem, and one alternative is to instead look at weaker symmetries than polymorphisms, so-called partial polymorphisms. Intuitively, while a partial polymorphism does not give a complete recipe for how solutions can be combined to solve a problem efficiently, even a partial description might be sufficient to avoid the need of trying all possible combinations. With the help of this approach I have for example studied the borderline between tractability and intractability, concentrating on hard problems suspected to be very close to this invisible barrier, which led to the identification of the easiest NP-complete satisfiability problem. More recently, this approach has also been applied to study kernelization properties of constraint satisfaction problems, and we have shown that the existence of certain types of partial polymorphisms are indeed sufficient to obtain significantly faster, although still exponential, algorithms. However, this algebraic approach is still in its infancy, and many questions remain unresolved.

### Explain like I’m five summary

There are good and bad methods to solve problems. Some problems appear to be really hard to solve, and only bad methods are known. With the help of algebra I try to make bad methods slightly better. Essentially I’m trying to draw a picture which explains how the hard problems are related to each other.

## CV in brief

### Employment History

• November 2022 –, Associate professor (universitetslektor) at TCSLAB, Linköping University, Sweden.
• May 2020 – October 2022, Assistant professor (biträdande universitetslektor) at TCSLAB, Linköping University, Sweden.
• April 2018 – April 2020, Postdoctoral researcher at TCSLAB, Linköping University, Sweden.
• March 2016 – March 2018, Postdoctoral researcher at the institute of algebra, Technische Universität Dresden, Germany.
• November 2012 – Februari 2016, PhD student at TCSLAB, Linköping University, Sweden.
• Juli 2012 – October 2012, Research assistant at TCSLAB, Linköping University, Sweden

• 2020 Habilitation (docent), Linköping University, Sweden.
• 2016 PhD in Computer Science, Linköping University, Sweden. Thesis Title: Strong Partial Clones and the Complexity of Constraint Satisfaction Problems: Limitations and Applications. Advisor: Peter Jonsson.
• 2012 M.Sc in Computer Science, Linköping University, Sweden. Thesis Title: Restricted Constraint Satisfaction Problems and the Exponential-time Hypothesis. Examiner: Peter Jonsson.
• 2010 B.Sc in Computer Science, Linköping University, Sweden. Thesis Title: A Comparison of SL- and Unit-resolution Search Rules for Stratified Logic Programs. Examiner: Ulf Nilsson.

• Finkornig komplexitet för satisfierbarhets- och villkorsproblem (Fine-grained complexity of satisfiability and constraint satisfaction problems). The Swedish Research Council, starting grant, 2020-01-01
• Recipient of the 2017 young researcher price of the Ruth and Nils-Erik Stenbäck foundation

### Refereeing

• Reviewer for the American Mathematical Society (AMS).
• Program committee member for the 29th International Joint Conference on Artificial Intelligence and the 17th Pacific Rim International Conference on Artificial Intelligence (ĲCAI-PRICAI-2020).
• Referee for several international conferences and journals in computer science, including the International Conference on Principles and Practice of Constraint Programming (CP), the ACM-SIAM Symposium on Discrete Algorithms (SODA), the International Colloquium on Automata, Languages and Programming (ICALP), and the International Symposium on Theoretical Aspects of Computer Science (STACS).
• Expert referee for three grant proposals from Agence Nationale de la Recherche (ANR), the Czech Science Foundation (GACR), and the Austrian science Fund (FWF).

### Workshops and Seminars

• Speaker at Logic and Search (LASH-2017), Melbourne, Australia, 2017.
• Invited speaker at QuantLA research seminar, Dresden, Germany, 2017.
• SAT and Interactions, Dagstuhl, Germany, 2016.
• Speaker at Workshop on Qualitative Spatial and Temporal Reasoning (QUAC-2015), Dresden, Germany, 2015.

### Supervision

• Main supervisor of Leif Eriksson, PhD student, TCSLAB, Linköping University.
• Secondary supervisor of Baril Ambroise, PhD student, Université de Lorraine.
• Secondary supervisor of George Osipov, PhD student, TCSLAB, Linköping University.
• Secondary supervisor of Biman Roy, PhD student, TCSLAB, Linköping University. Thesis title: Applications of Partial Polymorphisms in (Fine-Grained) Complexity of Constraint Satisfaction Problems, 2020.
• Examiner of Leif Eriksson, master’s student, Linköping University. Thesis title: Solving Temporal CSPs via Enumeration and SAT Compilation, 2019.
• Supervisor of Adam Shi, master’s student, Linköping University. Thesis title: Automatic Enumeration
of Intervals of Partial Co-Clones, 2016.

## Publications

### 2023

Leif Eriksson, Victor Lagerkvist (2023) Improved Algorithms for Allen's Interval Algebra by Dynamic Programming with Sublinear Partitioning Proceedings of the 32nd International Joint Conference on Artificial Intelligence, p. 1919-1926 (Conference paper)
Peter Jonsson, Victor Lagerkvist (2023) General Lower Bounds and Improved Algorithms for Infinite-Domain CSPs Algorithmica, Vol. 85, p. 188-215 (Article in journal)
Leif Eriksson, Victor Lagerkvist (2023) A Fast Algorithm for Consistency Checking Partially Ordered Time Proceedings of the 32nd International Joint Conference on Artificial Intelligence, p. 1911-1918 (Conference paper)
Peter Jonsson, Victor Lagerkvist (2023) General Lower Bounds and Improved Algorithms for Infinite-Domain CSPs Algorithmica, Vol. 85, p. 188-215 (Article in journal)

### 2022

Leif Eriksson, Victor Lagerkvist (2022) A Multivariate Complexity Analysis of Qualitative Reasoning Problems Proceedings of the 31st International Joint Conference on Artificial Intelligence (IJCAI-22), p. 1804-1810 (Conference paper)