Algorithms and Complexity Theory

The Algorithm and Complexity Theory group studies the complexity of computational problems raised in all fields of Computer Science. The study of complexity has two directions. One is devising efficient algorithms, yielding an upper bound of the complexity. The other is to prove the impossibility of solving the problem in bounded computational resources, thus giving a lower bound of the complexity. The true complexity is found once the two bounds meet, which establishes a thorough understanding of the problem and motivates the community to move on to other problems. The topics in this field include algorithms, data structures, probabilistic structures, combinatorial optimization, parallel computation, quantum computation, complexity theory, communication complexity, scientific computing, to name a few.

Research Themes