Philipp Weis: Formula Size and Number of
Variables in Descriptive Complexity
In descriptive complexity, we characterize computational problems by the
richness of a logic required to express the problem. Measures of complexity
include formula size, quantifier depth and number of variables. In this talk
I will survey classical results that relate natural complexity classes,
including AC^1, P and PSPACE, to first-order languages with different bounds
on formula size. I will also survey more recent work on the trade-off
between formula size and the number of variables and discuss some open
problems.