Universiteit van Amsterdam

Events

Institute for Logic, Language and Computation

Please note that this newsitem has been archived, and may contain outdated information or links.

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

Speaker: Anuj Dawar (Cambridge)
Date: 21-23 June 2016
Location: Room F1.15, ILLC, Science Park 107, Amsterdam

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

Please note that this newsitem has been archived, and may contain outdated information or links.