Theoretical Computer Science

Theoretical computer science aims to explore the foundations of computer science, especially from the mathematical point of view. There are two major directions within, namely algorithm design and complexity. In algorithm design, researchers aim to design algorithms with better performance guarantee or faster running time than the existing ones. In complexity theory, researchers study the relationship of different complexity classes with the final goal of settling the P versus NP problem. Our research groups mainly focus on designing efficient algorithms for real-world problems such as energy efficient scheduling, fair division and facility location problems. We are interested in exploring the optimal structures for different combinatorial problems and truthful mechanism designs in algorithmic game theory. We have been organizing summers schools on game theory and social choice several times, bringing together world experts in this field.

The Theory Group also publishes regularly in top conferences for AI theory like AAAI, IJCAI, and AAMAS.