The department’s research in this area studies fundamental aspects of computer science and aims at providing innovative solutions to algorithmic and complexity problems. Our strength lies in approximation algorithms, fixed-parameter algorithms, combinatorial optimization, communication complexity, computational complexity, cryptography, and quantum computing. Our recent work focuses on

  • Hardness of approximation of constraint satisfaction problems
  • Limitation of convex optimization algorithms
  • Fixed-parameter tractable algorithms
  • Quantum algorithms and computational complexity
  • Pseudorandomness, randomness extraction, and computational lower bounds
  • Complexity and security of cryptographic primitives

Academic staff: BOGDANOV Andrej, CAI Leizhen, CHAN Siu On, YAO Chi Chih Andrew, and ZHANG Shengyu