Chennai Mathematical Institute


10.45 a.m.
Logics with Matrix Rank Operators

Anuj Dawar
Cambridge University, UK.


I will look at recent work studying extensions of first-order logic and fixed-point logic with operators for computing the rank of matrices. It is shown that these can define the various polynomial-time problems that are not definable in fixed-point logic with counting. I will look at games for characterising expressibility in this logic and conclude with a number of open problems.