Logics with Matrix Rank Operators
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.