BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Talks.cam//talks.cam.ac.uk//
X-WR-CALNAME:Talks.cam
BEGIN:VEVENT
SUMMARY:Locally Finite Constraint Satisfaction Problems - Joanna Ochremiak
 \, University of Warsaw
DTSTART:20150515T130000Z
DTEND:20150515T140000Z
UID:TALK58292@talks.cam.ac.uk
CONTACT:Jonathan Hayman
DESCRIPTION:Many natural computational problems\, such as satisfiability a
 nd\nsystems of equations\, can be expressed in a unified way as constraint
 \nsatisfaction problems (CSPs). They can be understood as asking whether\n
 there is a homomorphism between two relational structures over the\nsame s
 ignature. We consider structures whose elements are built of\nso-called at
 oms\, and defined using finitely many FO formulas. Both the\ndomain and th
 e number of relations of such structures are usually\ninfinite\, but thank
 s to the finite presentation they can be treated as\nan input for algorith
 ms.\n\nA relational structure T is locally finite is every relation of T i
 s\nfinite. We use recent results in topological dynamics to prove that it\
 nis decidable whether there exists a homomorphism from a relational\nstruc
 ture A to a locally finite relational structure T. As a\ncorollary\, we ef
 fectively characterize certain subclasses of CSPs\nsolvable in polynomial 
 time\, with applications to descriptive complexity\n.\n\nJoint work with B
 artek Klin\, Eryk Kopczyński and Szymon Toruńczyk.
LOCATION:Computer Laboratory\, William Gates Building\, Room FW11
END:VEVENT
END:VCALENDAR