University COVID-19 update

The University of Waterloo is constantly updating our most Frequently Asked Questions.

Questions about buildings and services? Visit the list of Modified Services.

Please note: The University of Waterloo is closed for all events until further notice.

Universal algebraExport this event to calendar

Thursday, January 17, 2013 — 3:30 PM EST

Ross Willard, Department of Pure Mathematics, University of Waterloo

Graphs, posets, polymorphisms, and the Constraint Satisfaction Problem Dichotomy Conjecture"

To kick of this term's seminar, I will briefly present all the main themes at play in current work on the Constraint Satisfaction Problem Dichotomy Conjecture. The ingredients are (1) finite graphs, posets, and other more general finite structures; (2) colouring/homomorphism problems obtained from a finite structure; (3) "idempotent polymorphisms" of a finite struc-
ture; (4) identities involving idempotent polymorphisms forcing varying degrees of nontriviality (called "Maltsev conditions"); (5) the "primitive-positive-interpretability" relation between - finite structures. I will have identify each of the main Maltsev conditions relevant to CSP and some secondary ones, characterize each main Maltsev condition by a class of structures which it forbids to be pp-interpretable, and state the conjectures connecting each main Maltsev condition to a computational complexity class.

Note: this is a 90-minute seminar.
 

Location 
MC - Mathematics & Computer Building
5046
200 University Avenue West

Waterloo, ON N2L 3G1
Canada

S M T W T F S
26
27
28
29
30
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
1
2
3
4
5
6
  1. 2020 (67)
    1. May (3)
    2. March (16)
    3. February (26)
    4. January (22)
  2. 2019 (199)
    1. December (7)
    2. November (26)
    3. October (19)
    4. September (13)
    5. August (7)
    6. July (12)
    7. June (18)
    8. May (22)
    9. April (11)
    10. March (25)
    11. February (17)
    12. January (22)
  3. 2018 (219)
  4. 2017 (281)
  5. 2016 (335)
  6. 2015 (209)
  7. 2014 (235)
  8. 2013 (251)
  9. 2012 (135)