Until March 11th the seminars meet on Zoom on Thursdays 4:10—5:00pm UTC.
Starting March 18th we switch to daylight saving time and so the seminars will be meeting on Thursdays 3:10—4:00 UTC.
4:10pm UTC is
6:10 am Hawaii Standard Time (UTC-10)
8:10 am Pacific Standard Time (UTC-8)
9:10 am Mountain Standard Time (UTC-7)
10:10 am Central Time (UTC-6)
11:10 am Eastern Standard Time (UTC-5)
4:10 pm Greenwich Mean Time (UTC+0)
5:10 pm Central European Time (UTC+1)
3:10 am on Friday Australian Eastern Daylight Time (UTC+11)
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.