Skip to content Skip to navigation

Computational Complexity Theory

Non-CS Faculty:

Associated Projects

Eric Allender

Some computational problems require more resources than others.

The goal of this activity is to understand the interplay between information and complexity. The current focus centers on computational complexity classes.  Complexity classes provide the best tool currently available for understanding the computational complexity of real-world computational problems. Some of these problems are notoriously difficult, but recent progress justifies some optimism that additional useful insight about these complexity classes can be obtained.