July 20, 2024
July -August, 2011
Summer Thematic Program on the Mathematics of Constraint Satisfaction

August 2-6, 2011
Workshop on Algebra and CSPs

Organized by:
Libor Barto (Charles University and McMaster University)
Andrei Krokhin (Durham University)
Ross Willard (University of Waterloo)


The main goal of this workshop is to highlight the recent advances on the CSP Dichotomy Conjecture arising from the algebraic approach. It will focus on the various algebraic notions and results that have been developed in the attempts to resolve this conjecture and connected problems and will also include presentations on related algebraic topics, such as Maltsev Conditions and Tame Congruence Theory. The workshop may also include presentations on CSPs over infinite templates, quantified CSPs, and connections with logic, finite model theory, and complexity.


Manuel Bodirsky (Ecole Polytechnique, Palaiseau)
Andrei Bulatov (Simon Fraser University)
Victor Dalmau (UPF, Barcelona)
Martin Dyer (University of Leeds)
Peter Jeavons (University of Oxford)
Vladimir Kolmogorov (University College, London)
Marcin Kozik (Jagiellonian University)
Benoit Larose (Champlain College)
Miklos Maroti (University of Szeged)
Barnaby Martin (Durham University)
Ralph McKenzie (Vanderbilt University)
Michael Pinsker (TU Vienna)
Johan Thapper (École Polytechnique)

Workshop Schedule (invited talk titles and abstracts, contributed talk abstracts)

Tuesday August 2
9:20 - 9:30 Welcome and Introduction
9:30 - 10:30 Libor Barto (McMaster University)
A welcome conservative talk
10:30 - 11:00 Coffee Break
11:00 - 12:00 Marcin Kozik (Jagiellonian University)
CSPs with near-unanimity polymorphisms are solvable by linear Datalog
12:00 - 2:00 Lunch Break
2:00 - 3:00 Ralph McKenzie (Vanderbilt University) Link 1 Link 2
Finitely related clones and algebras with cube-terms; Valeriote's conjecture for finite algebras in congruence modular algebras and its consequence for the CSP dichotomy conjecture
3:00 - 3:30 Coffee Break
3:30 - 4:00 Laszlo Zadori (University of Szeged)
Near unanimity operations and totally symmetric idempotent operations on reflexive digraphs
4:00 - 4:30 Alexandr Kazda (Charles University in Prague)
Dichotomy for conservative digraphs
4:30 - 5:30 Reception
Fields Atrium - cash bar
Wednesday August 3
9:30 - 10:30 Miklos Maroti (University of Szeged) Link 1 Link 2
Beyond bounded width and few subpowers
10:30 - 11:00 Coffee Break
11:00 - 12:00 Andrei Bulatov (Simon Fraser University)
Conservative dichotomy revisited
12:00 - 2:00 Lunch Break
2:00 - 3:00 Martin Dyer (University of Leeds)
On the complexity of # CSP
3:00 - 3:30 Coffee Break
3:30 - 4:00 Jakub Bulin (Charles University in Prague)
Absorption in finitely related SD(meet) algebras has bounded arity

Thursday August 4
9:30 - 10:30 Michael Pinsker (Université Denis Diderot - Paris 7)
Making the infinite finite: Polymorphisms on Ramsey structures
10:30 - 11:00 Coffee Break
11:00 - 12:00 Manuel Bodirsky (École Polytechnique)
Homogeneous Structures and Siggers Terms
12:00 - 2:00 Lunch Break
2:00 - 3:00 Barnaby Martin (Durham University) Link 1 Link 2
A tetrachotomy for positive equality-free logic
3:00 - 3:30 Coffee Break
3:30 - 4:00 Hubie Chen (Univ. Pompeu Fabra)
Generic Expression Hardness Results for Primitive Positive Formula Comparison
Friday August 5
9:30 - 10:30 Peter Jeavons (University of Oxford)
A Galois Connection for Valued Constraints
10:30 - 11:00 Coffee Break
11:00 - 12:00 Vladimir Kolmogorov (University College London)
The complexity of conservative valued CSPs
12:00 - 2:00 Lunch Break
2:00 - 3:00 Johan Thapper (École Polytechnique)
Min CSP on Four Elements: Moving Beyond Submodularity
3:00 - 3:30 Coffee Break
3:30 - 4:00 Venkatesan Guruswami (CMU)
Saturday August 6
9:30 - 10:30 Victor Dalmau (Universitat Pompeu Fabra)
Robust approximation of CSPs
10:30 - 11:00 Coffee Break
11:00 - 12:00 Benoit Larose (Champlain Regional College)
NU operations, graphs and finite duality
12:00 - 2:00 Lunch Break
2:00 - 3:00 open problem session
3:00 - 3:30 Coffee Break


Confirmed Participants

Full Name University/Affiliation
Andrews, Rob (no affiliation)
Barto, Libor McMaster University
Bergman, Cliff Iowa State University
Bodirsky, Manuel École Polytechnique
Bulatov, Andrei Simon Fraser University
Bulín, Jakub Charles University in Prague
Capes, Tim University of Toronto
Carvalho, Catarina University of Hertfordshire
Chaplick, Steven University of Toronto
Chen, Hubie Univ. Pompeu Fabra
Creed, Páidí Queen Mary, University of London
Dalmau, Victor Universitat Pompeu Fabra
Davis-Mendelow, Sammy University of Toronto
Delic, Dejan Ryerson University
Dyer, Martin University of Leeds
Egri, Laszlo McGill University
Failing, David Iowa State University
Foniok, Jan Queen's University
Ghasemloo, Kaveh University of Toronto
Guenda, Kenza University of Algiers
Guruswami, Venkatesan Carnegie Mellon University
Han, Changho University of Toronto
Hart, Bradd McMaster University
Holmes, Tristan University of Hawaii at Manoa
Horowitz, Jonah McMaster University
Huang, Jing University of Victoria
Huber, Anna Durham University
Hubicka, Jan Institute of theoretical computer science (ITI)
Hyndman, Jennifer University of Northern British Columbia
Jeavons, Peter University of Oxford
Karamad, Ehsan University of Toronto
Kazda, Alexandr Charles University in Prague
Kolmogorov, Vladimir University College London
Kozik, Marcin Jagiellonian University
Krokhin, Andrei Durham University
Lampe, William A. University of Hawaii
Larose, Benoit Champlain Regional College
Lemaître, Adrien Université de Montréal
Lian, Annie York University
Marecek, Jakub The University of Nottingham
Markovic, Petar University of Novi Sad
Maróti, Miklós University of Szeged
Martin, Barnaby Durham University
Mason, Jesse University Of Northern British Columbia
McIlraith, Sheila University of Toronto
McKenzie, Ralph Vanderbilt University
Muise, Christian University of Toronto
Niven, Todd La Trobe University
Pinsker, Michael Université Denis Diderot - Paris 7
Pitassi, Toniann University of Toronto
Portier, Natacha ENS Lyon
Promislow, David York University
Rahman, Mustazee University of Toronto
Seif, Steve University of Louisville
Smedberg, Matthew Vanderbilt University
Stacho, Juraj University of Haifa
Szendrei, Agnes University of Colorado
Thapper, Johan École Polytechnique
Tooming, Laur University of Tartu
Valeriote, Matthew McMaster University
Vargas Garcia, Edith Mireya TU-Dresden
Wen, Yuting University of Waterloo
Wild, Marcel University of Stellenbosch
Willard, Ross University of Waterloo
Wires, Alexander Vanderbilt University
Wrona, Michal Wroc?aw University of Technology
Zadori, Laszlo University of Szeged
Zhou, Yuan Carnegie Mellon University
Zivny, Stanislav Oxford University
Zouzias, Anastasios University of Toronto

Program Researchers

Program Participants requesting support or office space:
All scientific events are open to the mathematical sciences community. Visitors who are interested in office space or funding are requested to apply by filling out the application form.
Fields scientific programs are devoted to research in the mathematical sciences, and enhanced graduate and post-doctoral training opportunities. Part of the mandate of the Institute is to broaden and enlarge the community, and to encourage the participation of women and members of visible minority groups in our scientific programs.

For additional information contact thematic(PUT_AT_SIGN_HERE)

Back to Top