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.
A brief history of the Constraint Satisfaction Problem
Jan. 14, 2021 1pm (Zoom (vir…
Rep Theory
Shashank Kanade (University of Denver)
X
Principal characters of standard (i.e., highest weight, integrable) modules for affine Lie algebras have been a rich source of q-series and partition identities. The algebra A_1^{(1)} (or, sl_2^) was "understood" in this sense a few decades ago. On q-series side, this leads to identities of Gordon-Andrews and Andrews-Bressoud. In this talk, I'll present q-series identities related to the next "simplest" affine Lie algebra, namely, A_2^{(2)}. Here, we get six families of q-series identities confirming a conjecture of McLaughlin and Sills. The main machinery used is that of Bailey pairs and Bailey lattices. This is a joint work with Matthew C. Russell. (N.B.: These q-series include Vir(3,p) minimal model characters.)
A brief history of the Constraint Satisfaction Problem