Electrical Engineering and Computer Science

Complexity Theory

Research Areas -> Theory of Computation -> 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.
 
Faculty
Schoenebeck, Grant
Shi, Yaoyun