Descriptive Complexity measures the richness of a language or sentence needed to describe a given property. The languages are variants of first-order logic and their targets are finite, ordered structures. There is a profound relationship between the traditional computational complexity of a problem and the descriptive complexity of the problem. Indeed, all major complexity classes have been shown to have natural descriptive characterizations.
This research broadens the connections and extends the knowledge of complexity. The following three areas are being pursued: (1) Dynamic Complexity, (2) Model Checking and (3) Tradeoffs in Descriptive Complexity.
