Banff, day 1

The first day of the meeting is over. We met in the well-appointed lecture room at BIRS, on the Banff Centre campus, with its comfortable seating:


We have also had the group photo taken:

Group photo

The first day was devoted to tutorials. Michael Pinsker gave two excellent talks about infinite constraint satisfaction problems, summarised in the slogan “Model theory, universal algebra, Ramsey theory, topological dynamics → Theoretical computer science”. He explained with care and humour what a CSP is, why it can be a feasible computational problem even when the template is infinite (so, for example, an instance of Graph-SAT is a CSP over an appropriate reduct of the random graph), what Fraïssé’s theorem says, what ω-categorical structures are and what is the relation to oligomorphic permutation groups, what a function clone is and why it is important for CSP (the complexity of CSP over an ω-categorical template Γ depends only on the clone of polymorphisms of Γ), how the topology of pointwise convergence comes into the act, why Ramsey structures are important for the theory (they enable the existence of functions with certain properties in the clone to be reduced to the existence of “canonical” functions), and lots more. As an example he gave a simple proof that the betweenness problem is NP-complete. (We are given a set of triples and want to know if they are instances of the betweenness relation relative to some linear order on the domain.)

It was a rapid crash course in some beautiful and important mathematics. You can watch videos of his two talks so far on the workshop website, and I guess his slides will appear there soon as well.

Ross Willard gave a tutorial on the relation between CSPs and universal algebra. I am not sure whether the organisers offered him three hours or just two, but in the event he only took a single hour. If I thought Michael Pinsker crammed a lot in, Ross left him in the shade. Hard stuff like tame congruence theory with its specialisation to idempotent algebras (the important ones for CS), as well as Maltsev identities, clones, and absorption, were all covered, by dint of not giving us precise definitions of some of the things, but rather explaining what was really important. He is also on video on the workshop website.

Oh, and there was some guy talking about synchronization as well.

At lunchtime I went on a (mathematical) family outing: with my son and grandson, I climbed Tunnel Mountain, height 1692 metres, but only a few hundred metres climb from the Banff Centre, and dwarfed by some of the magnificent mountains round about:

Family outing


About Peter Cameron

I count all the things that need to be counted.
This entry was posted in events, exposition, geography and tagged , , , , , , . Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s