2nd Semester 2015/16: Definability and Complexity of Counting Logics

Instructors

Anuj Dawar (University of Cambridge)
If you are interested in this tutorial, please contact Benedikt Loewe by email.

ECTS

2

Description

Lecture 1.

Tuesday, 21 June (13-15), room F1.15 (ILLC Seminar Room). Definability in Counting Logics (slides)

First-order logic with counting. Fixed-point logic with counting. Relation to complexity. Definability of constraint satisfaction problems.

Key reference:

Albert Atserias, Andrei A. Bulatov, Anuj Dawar: Affine systems of equations and counting infinitary logic. Theor. Comput. Sci. 410(18): 1666-1683 (2009)

Lecture 2.

Wednesday, 22 June (13-15), room F1.15 (ILLC Seminar Room). Definability of Linear Programming Problems (slides)

Combinatorial Optimization problems and their Linear Programming Relaxations. Issues of Symmetry and Definability.

Key reference:

Matthew Anderson, Anuj Dawar, Bjarki Holm: Solving Linear Programs without Breaking Abstractions. J. ACM 62(6): 48 (2015)

Lecture 3.

Thursday, 23 June (11-14), room F1.15 (ILLC Seminar Room). Logic and Circuit Complexity (slides)

Relationship between definability and circuit complexity for first-order logic, fixed-point logic and counting logics.

Key reference:

Matthew Anderson, Anuj Dawar: On Symmetric Circuits and Fixed-Point Logics. STACS 2014: 41-52

The lectures take place on Tuesday, 21 June (13-15), Wednesday, 22 June (13-15), and Thursday, 23 June (11-14) in room F1.15 (ILLC Seminar Room). Participants are expected to read the "key reference" before the lectures. In order to get the 2 ECTS credits for this project, you need to submit a written summary of approximately five pages, containing a one-page summary of Atserias-Bulatov-Dawar, a one-page summary of Anderson-Dawar-Holm, a one-page summary of Anderson-Dawar, and a two-page personal commentary about the actual tutorial lectures (what did you learn? what did you like? what would you like to learn next?). This document has to be submitted by 15 July 2016 to b.loewe@uva.nl and will be graded on a PASS/FAIL basis.