Chennai Mathematical Institute

Seminars




10.45 a.m.
Logics with Matrix Rank Operators

Anuj Dawar
Cambridge University, UK.
23-12-09


Abstract

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.