Developing algorithms to better solve counting constraint satisfaction problems

By Andrew Ringer

If you’ve ever completed a sudoku puzzle, then you’ve completed a constraint satisfaction problem (CSP). This type of problem is defined as a mathematical question where a number of constraints or limitations must be satisfied. SFU computing science professor Andrei Bulatov, one of the world’s leading researchers on CSPs, develops algorithms to analyze these types of problems.

In Sudoku, the constraints that need to be satisfied can be found within the rules: all 81 squares need to be filled out with a single number, only the numbers 1-9 can be used, and each 3x3 square, vertical column and horizontal row must contain each number only once. These problems can be challenging as is, but imagine the difficulty of the problem if it is scaled up to 256 squares, 625 squares or even larger?

Of course, Sudoku represents just one kind of the infinite amount of CSPs that exist, and the constraints for these problems are not often so easily defined. This makes developing an algorithm to solve a group of these problems a daunting task. Bulatov, a mathematician by training and study, has been analyzing these types of problems for the past two decades.

“The goal is to come up with solution algorithms for the CSP or explain why such an algorithm is unlikely to exist,” says Bulatov.

“This helps to advance our understanding of a large number of specific problems that have been studied in theoretical computer science and elsewhere.”

In addition to CSPs, Bulatov also researches counting constraint satisfaction problems (CCSPs). The main difference between these types of problems is that the former focuses on finding out if a solution exists for a problem, while the latter focuses on finding out how many solutions exist.

Bulatov developed an algebraic approach to solve both CSPs and CCSPs by using a group of methods based on universal algebra. The main idea behind this approach is looking at symmetries within a problem to make conclusions. These conclusions include classifying whether a problem or group of problems is solvable or not.

“In the very large class of computational problems, their complexity and how we construct algorithms for those problems depends entirely on symmetries,” says Bulatov.

His paper titled The Complexity of the Counting Constraint Satisfaction Problem, originally presented at the Association for Computing Machinery conference in 2013, is considered an influential work for CCSP research.

Recently, Bulatov’s contributions to the field were recognized as he was one of five researchers to receive the Gödel Prize for their work on the classification of the counting complexity of CSPs. The Gödel Prize awards outstanding papers in the area of theoretical computer science and is named after famous logician Kurt Gödel. It is considered the most prestigious prize in the area of theoretical computer science for a specific work. Bulatov is only the second researcher to receive this prize in Canada after Charles Rackoff in 1993, the first year the prize was awarded.

“It’s very pleasant to get this recognition for my research,” says Bulatov.

As he continues his research, Bulatov is focused on seeing how the algebraic approach can be applied to other types of computational problems. While this fundamental research has known applications in theoretical computing science, Bulatov is interested in seeing how far he can push the boundaries in applying this approach to other research areas.