27 August 2024

On the 3rd of June, George Osipov at the Department of Computer and Information Science (IDA) successfully defended his thesis in the intersection of theoretical computer science and artificial intelligence (AI), with a focus on parameterized complexity of constraint satisfaction problems (CSPs).

image cut from thesis cover

Congratulations on your PhD! What was your background when you started your PhD?
"I have a bachelor's degree in computer science from Free University of Tbilisi in Georgia (where I'm from) and two years in a master's program in Mathematics at Ilia State University in Georgia with one Erasmus year in Uppsala."

What is it like to be a PhD student at IDA?
"My time as a PhD was quite pleasant overall. Despite having no prior research experience, close support from my supervisors helped me get up to speed quite quickly, and I have been enjoying research ever since. I was part of Wallenberg AI autonomous systems and software program (WASP) graduate school, which made the experience even more interesting with various courses around Sweden, summer and winter schools and international trips."

You have just finished your PhD. What do you want to do next?
"I am continuing to work on research directions that emerged in the later years of my PhD, now with the help of an International postdoc grant from the Swedish Research Council. It allows me to travel for two years outside Sweden, and my plan is to visit two universities in the UK: Oxford University and Royal Holloway University of London."

A summary of the thesis by George Osipov

Many real-world tasks can be phrased in terms of assigning values to variables subject to a set of constraints. This makes the Constraint Satisfaction Problem (CSP) a versatile modelling tool both in practice and in theory of computing. In applications, it is often impossible to satisfy all constraints, but there exist assignments that satisfy almost all constraints.

In his thesis, George Osipov has studied the complexity of solving almost satisfiable CSPs. Classical complexity theory strongly suggests that finding optimal assignments to CSPs is computationally intractable. However, by adopting the lens of parameterized complexity, many problems become tractable by leveraging the special structure of the instances. The thesis is at the intersection of theoretical computer science and AI and is not guided by an immediate application. One possible application is efficient data processing and automatic reasoning, which can be crucial for drawing insights from the drastically increasing amounts of data. An attractive feature of parameterized algorithms in this regard is that they scale favourablyto larger inputs.

To the thesis: On Infinite-Domain CSPs Parameterized by Solution Cost

Read more about George Osipov

Doctoral studies in computer and information science

More about WASP at IDA

Organisation

Latest news from LiU

A man in a lab applies water to the surface of a yellow-green material.

More effective production of “green” hydrogen with new combined material

Hydrogen produced from water is a promising renewable energy source – especially if the hydrogen is produced using sunlight. Now LiU researchers show that a combination of new materials improves the efficiency of the chemical reaction several times.

Demonstration of MR elastography.

Fatty liver – but not liver damage – common in type 2 diabetes

Six out of ten people with type 2 diabetes had fatty liver in a new study. Of these, only a small percentage had developed more severe liver disease. Type 2 diabetes in combination with obesity is linked to a greater risk.

Black and white picture of a man on the moon wearing a space suit

The Hasselblad Foundation supports dome film about the moon landings

Visualization Center C in Norrköping is creating a new 3D full dome production to take the audience on a journey back to the moon landings. The Hasselblad Foundation has contributed funding for the film Once Upon the Moon.