Perhaps the hardest thing to prove about a computational model is that it cannot solve a given problem within particular resource constraints. Such ``lower bounds'' are currently obtainable only when the model is very specialized or the constraints are very severe. The research project in Low-Level Complexity conducted by our group attempts to attack such problems by determining the relationships between complexity classes defined in various models by such very severe constraints.
Another project in complexity research studies the area called Descriptive Complexity. Computational complexity was originally defined in terms of the natural entities of time and space, and the term complexity was used to denote the time or space used in the computation. Rather than checking whether an input satisfies a property S, a more natural question might be, what is the complexity of expressing the property S? These two issues -- checking and expressing -- are closely related. It is startling how closely tied they are when the latter refers to expressing the property in first-order logic of finite and ordered structures.
Professors David A. Mix Barrington and Neil Immerman of our group conduct research in computational complexity theory.
Kazu Hirata Audrey Lee
Bill Hesse Chi-Jen Lu Kousha Etessami Jose Antonio Medina-Peralta Sushant Patnaik