Faculty Colloquium: Complexity Classifications of Valued Constraint Satisfaction Problems. Speaker: Vladimir Kolmogorov, IST Austria

November 29, 16:40 – 18:00 

Complexity Classifications of Valued Constraint Satisfaction Problems

Classifying complexity of different classes of optimization problems is an important research direction in Theoretical Computer Science. One prominent framework is Valued Constraint Satisfaction Problems (VCSPs) in which the class is parameterized by a "language", i.e. a set of cost functions over a fixed discrete domain. An instance of the problem is an arbitrary sum of functions from the language (possibly with overlapping variables), with the goal to minimize the sum. This framework can capture many classes of optimization problems such as 3-SAT, graph coloring, minimum vertex cover, submodular minimization, and others.

A series of recent papers, culminating with the works of D. Zhuk and A. Bulatov in 2017, has established a complete complexity classification of arbitrary languages. I will describe our contributions to this topic. One of the results is a reduction from general VCSPs to plain CSPs (i.e. to languages with {0, infinity}-valued functions). The key algorithmic tool that we use is a certain LP relaxation of the problem combined with the algorithm for plain CSPs.

In the second part of the talk, I will consider a version of the CSP framework where each variable must appear in exactly two constraints. It captures, in particular, the class of perfect matching problems, which can be solved by the Edmonds's blossom-shrinking algorithm. I will present a generalization of this algorithm that can handle "even Delta-matroid constraints". As a consequence of this, we settle the complexity classification of planar Boolean CSPs started by Dvořák and Kupec.

Colloquium

Venue:

Moscow, Kochnovsky pr.,3, room 205, 16:40 
Everyone interested is welcome to attend. 
If you need a pass to HSE, please contact computerscience@hse.ru