Locally Finite Constraint Satisfaction Problems

Add to your list(s) Download to your calendar using vCal

• Joanna Ochremiak, University of Warsaw
• Friday 15 May 2015, 14:00-15:00
• Computer Laboratory, William Gates Building, Room FW11.

If you have a question about this talk, please contact Jonathan Hayman.

Many natural computational problems, such as satisfiability and systems of equations, can be expressed in a unified way as constraint satisfaction problems (CSPs). They can be understood as asking whether there is a homomorphism between two relational structures over the same signature. We consider structures whose elements are built of so-called atoms, and defined using finitely many FO formulas. Both the domain and the number of relations of such structures are usually infinite, but thanks to the finite presentation they can be treated as an input for algorithms.

A relational structure T is locally finite is every relation of T is finite. We use recent results in topological dynamics to prove that it is decidable whether there exists a homomorphism from a relational structure A to a locally finite relational structure T. As a corollary, we effectively characterize certain subclasses of CSPs solvable in polynomial time, with applications to descriptive complexity .

Joint work with Bartek Klin, Eryk Kopczyński and Szymon Toruńczyk.

This talk is part of the Logic and Semantics Seminar (Computer Laboratory) series.

This talk is included in these lists:

• All Talks (aka the CURE list)
• Cambridge talks
• Computer Laboratory, William Gates Building, Room FW11
• Computing and Mathematics
• Department of Computer Science and Technology talks and seminars
• Interested Talks
• Logic and Semantics Seminar (Computer Laboratory)
• School of Technology
• Trust & Technology Initiative - interesting events
• bld31
• tcw57’s list
• yk373's list

Note that ex-directory lists are not shown.