Electrical Engineering and Computer Science

Complexity Theory

Overview
Some computational tasks seem resilient to efficient solutions or even efficient approximation. When can we show that no efficient algorithm exists? What types of inputs are particularly difficult and why? What are the limits of quantum computing and parallelism? Besides the mathematical beauty of these questions, they have important applications to cryptography.
 

CSE Faculty

Peikert, Christopher
Schoenebeck, Grant
Shi, Yaoyun
Volkovich, Ilya