
July
August, 2011
Summer Thematic Program on the Mathematics of Constraint
Satisfaction
August 26,
2011
Workshop on Algebra and CSPs
Organized by:
Libor Barto (Charles University and McMaster University)
Andrei Krokhin (Durham University)
Ross Willard (University of Waterloo)


OVERVIEW:
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.
INVITED SPEAKERS:
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)
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 nearunanimity 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 cubeterms;
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 equalityfree 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 
DavisMendelow, 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 
TUDresden 
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 postdoctoral 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)fields.utoronto.ca
Back
to Top

