Under the leadership of the Turing Award laureate Professor Yao, we are aiming at fundamental researches in theoretical computer science. Our main research areas include analysis of algorithms, approximation algorithms, combinatorial optimization, communication complexity, computational complexity, cryptographic protocols, graph algorithms, graph theory, parameterized complexity, and quantum computing.

 

The following are some of our current activities:

1. Design efficient algorithms and study complexity theories in emerging new areas of theoretical computer science, such as quantum communication and computing.
2. Study the fixed-parameter tractability of various graph problems, especially fixed-cardinality optimization problems. In particular, we are developing a powerful random separation method for solving such problems.
3. Apply techniques from combinatorial optimization to design approximation algorithms for NP-hard problems, and investigate theoretical problems that arise from practical problems in computer networks.
4. Analyse linear programming relaxations of combinatorial optimization problems. We are developing the iterative relaxation method as a general method to design exact and approximation algorithms.