Starting March 18th we switch to daylight saving time and so the seminars will be meeting on Thursdays 15:10—16:00 UTC.
The meeting number on Zoom is 91561142408. There is no password, but we have a waiting room, so use a recognizable name.
The Constraint Satisfaction Problem is a problem where one is tasked with deciding the truth of the sentence "there exist values for variables x,y,... such that this conjunction of predicates on x,y,... holds." While CSP is a computational problem, it leads to many purely mathematical questions in logic, algebra, category theory, and combinatorics. CSP (and its variants) will be the main theme of this semester's Ulam seminar.
The complexity of CSP depends on the expressive power of the predicates that we allow. In the talk, we will look at the project of classifying the complexity of CSP on finite structures where there turned out to be a clear dividing line between "easy" and "hard" languages. We will also briefly introduce some common variants of CSP.
Polymorphims play a major role in the dichotomy proof for the complexity of the Constraint Satisfaction Problem. However, polymorphisms also help us better understand relational structures. A popular type of relational structure is the directed graph (digraph).
It turns out that polymorphisms of directed graphs are close to being as general as possible: Jakub Bulin, Dejan Delic, Marcel Jackson and Todd Niven have shown that for each relational structure A there is a digraph G such that A and G are, roughly speaking, the same with respect to having many types of polymorphisms. However, one notable exception are the so-called Maltsev polymorphisms; we will show that whenever a digraph has Maltsev polymorphism, it must also have a majority polymorphism. This is an implication not true in general relational structures.
The Promise Constraint Satisfaction Problem is a variant of the Constraint Satisfaction Problem (CSP). In PCSP, we are promised that either there exists a homomorphism from A to B, or there is even no homomrphism from A to a structure C; our goal is to decide between these two cases. An example of PCSP is PCSP(K_3,K_4), where we are deciding if the input graph is 3-colorable or not even 4-colorable.
The natural generalization of polymorphisms to pairs of structure are minions of polymorphisms. Minons have very little structure; compared to algebras we lose the ability to compose operations. Surprisingly, what little structure is left still leads to nontrivial mathematics.
In the talk, we will have a look at polymorphisms in general and polymorphisms from K_3 to K_4 in particular.
Graph coloring is a classic hard algorithmic problem. In promise graph coloring, we ask if at least an approximation is feasible: given a graph promised to be 3-colorable, say, can we efficiently find a 100-coloring? To prove that even this relaxed problem is hard, we study polymorphisms (think: algebraic relations between solutions). It turns out that in some cases, basic topological tools give a very direct understanding of those polymorphisms, seeing them as continuous maps from toruses to spheres. Joint work with Andrei Krokhin, Jakub Opršal, Stanislav Živný.
The Promise Constraint Satisfaction Problem (PCSP) is a generalization of the Constraint Satisfaction Problem (CSP) that includes approximation variants of satisfiability and graph coloring problems. In a [LICS '19] paper it was shown that a specific PCSP, the problem to find a valid Not-All-Equal solution to a 1-in-3-SAT instance, is not finitely tractable in that it can be solved by a trivial reduction to a tractable CSP, but such a CSP is necessarily over an infinite domain (unless P=NP). We further explore this phenomenon: we give a general necessary condition for finite tractability and characterize finite tractability within a class of templates - the "basic" tractable cases in the dichotomy theorem for symmetric Boolean PCSPs allowing negations by Brakensiek and Guruswami [SODA'18]. This is a joint work with Kristina Asimi.
Since deciding whether a given graph is 3-colourable is NP-complete, and checking validity of a colouring is an easy problem, also the problem of finding a colouring of a 3-colourable graph with 3 colours is a well-known NP-complete. One might be interested in a relaxed version of this problem, e.g., finding a colouring of a 3-colourable graph that uses 6 colours. This falls into a more general scope of so-called promise constraint satisfaction problem (PCSP). We will describe the basics of a theory characterising when one promise constraint satisfaction problem can be reduced to another using a gadget reduction.
Valued CSP is an optimization version of the Constraint Satisfaction Problem. Instead of finding any homomorphism from A to B, our goal in VCSP is to find a homomorphism that has a low cost. The complexity of VCSP is well understood with a dichotomy proved by Kolmogorov, Krokhin and Rolínek in 2015.
In this talk we will look at how to define the category of valued structures to get nice products in this cateogory. In particular, we will want weighted polymorphisms of a structure A to correspond to mappings from powers of A to A. This will require generalizing the notion of valued relational structure.
It is known that minion homomorphisms give very natural complexity reductions between (P)CSPs (Barto, Bulín, Opršal, Krokhin, 2019). We will explore how to translate these techniques into the valued CSP situation. Convex geometry will make an appearance.
I am going to present the dichotomy conjecture for CSPs of certain infinite templates, motivate this conjecture, and provide a rough overview of what we know about it.
The Counting CSP (#CSP), where the goal is to find or approximate the number of solutions of a CSP instance has been thoroughly studied from multiple perspectives. In this talk we study Counting CSPs, in which the goal is to find the number of solutions modulo a prime number p, denoted #_pCSP. We first show that the standard algebraic approach works (somewhat surprisingly) for this kind of problems, and then classify the complexity of modular counting for #_pCSP(H), where H is a graph.
Let A be a finite first-order structure and Phi a set of first-order formulas in its language with certain closure properties. We use a result about clonoids to show that the finitary relations on A definable by formulas in Phi are uniquely determined by the definable subsets of arity A^2. This gives new proofs of some finiteness results in Universal Algebraic Geometry. This talk is based on work of Erhard Aichinger and Bernardo Rossi.
A series of recent works have established the dichotomy of general-valued constraint satisfaction problems (VCSPs): every VCSP language can either be solved in polynomial time or is NP-hard. I will describe the algorithmic part of this dichotomy. As a key subroutine, we use a polynomial-time algorithm for ordinary CSPs satisfying a certain algebraic condition, whose existence was proved by Bulatov and by Zhuk in 2017. Joint work with Andrei Krokhin and Michal Rolinek (http://pub.ist.ac.at/~vnk/papers/VCSP.html ).
The Quantified Constraint Satisfaction Problem (QCSP) is the problem to evaluate a sentence of the form
"for all x1 exists y1 ... forall xn exists yn (R1(...) ∧ ... ∧ Rs(...))",
where R1, ..., Rs are relations from a constraint language Gamma. It is known that the complexity of the QCSP depends only on the algebra of polymorphisms of the constraint language. If all constraints are allowed then the QCSP is PSpace-complete. We will discuss what properties of the algebra place the problem in the class NP, what properties place it in the class co-NP, and how PSpace-hardness can be proved if the algebra has no such properties.
Barto and Kozik have introduced several weak consistency notions for CSPs, such as “Prague instances”, “weak Prague instances”, and “pq-consistency”, and have shown that any CSP template which can be solved by a local consistency algorithm can also be solved using one of these weak consistency notions. Their definition of “weak Prague instance” breaks up into three natural conditions on the directed graph of implications between single-variable restrictions, which they call (P1), (P2), and (P3). (P1) is the standard generalization of arc-consistency to CSPs with relations of higher arity, (P2) is a condition which is closely related to the basic linear programming relaxation of the instance, and (P3) is a condition which is closely related to the basic semidefinite relaxation of the instance. Barto and Kozik have raised the question of whether any instance of a bounded-width CSP which satisfies just (P1) and (P3) has a solution - this is a weaker consistency notion than all other consistency notions which are known to guarantee solvability. In this talk, I'll introduce an even weaker type of consistency than (P1) and (P3), and explain how we can use algebraic results about finite affine-free idempotent Taylor algebras in a purely black-box way to prove that this weaker consistency is strong enough to guarantee the existence of a solution. The algebraic input needed is a new type of subalgebra which I call a “stable subalgebra”, which satisfies some amazingly strong axiomatic rules.
Post completely described clones on a 2-element set; there are only countably many. Yanov and Muchnik proved that already on 3 elements, there are uncountably many clones. These results may also be viewed as results about 2-element and 3-element structures considered up to primitive positive interdefinability. Motivated by research in constraint satisfaction, a coarser equivalence relation on finite structures has been introduced recently, based on primitive positive (pp) constructions instead of primitive positive definitions. On the algebraic side, this amounts to studying idempotent linear strong Maltsev conditions for clones on finite sets. We do not know how many finite structures that are up to pp interconstructability; all uncountable families of structures on finite domains known to the speaker collapse down to countably many with respect to pp interconstructability. I will present some recent results about the special case of finite directed graphs, where at least we know the largest finite digraphs with respect to pp constructability. Joint work with Florian Starke, Albert Vucaj, and Dmitriy Zhuk
We investigate the semilattices of Mal'cev blocks ("SMB algebras"), a quasivariety of Taylor algebras invented by R. McKenzie and the speaker in 2009. The Constraint Satisfaction Problem over SMB algebras was proved to be tractable by A. Bulatov in 2017, and he used this case as a template for his proof of the Dichotomy Conjecture. In Bulatov's terminology of edge-colored graphs of algebras, SMB algebras are the prime example of as-connected algebras. Any simplification of the tractability proof for SMB algebras gives hope that one can, using Bulatov's theory of edge colored graphs of algebras, generalize to a simplification of the proof of the Dichotomy Theorem, motivating our investigation.
We were trying to prove D. Zhuk's reduction of "irreducible instances", which are consistent enough, to binary absorbing subuniverses ("Zhuk's Reduction Theorem") for the case of SMB algebras. We prove two results: One is a special case of Zhuk's Reduction Theorem, but assuming only 1-consistency, i.e. when all constraint relations are subdirect subuniverses of the product. The second result states that Zhuk irreducible instances, which are also Maroti reduced and consistent enough, must have a solution.