Descriptive complexity is an approach to complexity theory that measures the richness of a language or sentence needed to describe a given property. The language studied are variants of first-order logic and their targets are finite, ordered structures. In this setting, there is a non-trivial 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 project continues this research into descriptive complexity by concentrating on the following four research areas: (1) Order-independent languages; (2) First-order interpretations; (3) Applications to databases and dynamic complexity; (4) Trade-offs in descriptive complexity.
