21-23 June 2016, Tutorial "Definability and Complexity of Counting Logics"

Anuj Dawar, who is visiting from Cambridge, will give a three-part tutorial on 'Definability and Complexity of Counting Logics'.

Part 1 (21 June 13:00-15:00) covers first-order logic with counting, fixed-point logic with counting, relations to complexity, and definability of constraint satisfaction problems.
Literature: Albert Atserias, Andrei A. Bulatov, Anuj Dawar: Affine systems of equations and counting infinitary logic. Theor. Comput. Sci. 410(18): 1666-1683 (2009)

Part 2 (22 June 13:00-15:00) covers combinatorial optimization problems and their linear programming relaxations and issues of symmetry and definability.
Literature: Matthew Anderson, Anuj Dawar, Bjarki Holm, Solving Linear Programs without Breaking Abstractions, J. ACM 62(6): 48 (2015)

Part 3 (23 June 11:00-14:00) covers the relationship between definability and circuit complexity for first-order logic, fixed-point logic and counting logics.
Literature: Matthew Anderson, Anuj Dawar: On Symmetric Circuits and Fixed-Point Logics. STACS 2014: 41-52

For more information, please contact bloewe at science.uva.nl