The research of the institute of theoretical computer science mainly focuses on the areas including theoretical computer science, theory of interaction, computational complexity, knowledge engineering, programming language, computer economics, combinatorial optimization and mechanical design. There are 8 scholars and around 40 graduate students in this institute. Prof. Yuxi Fu is the current director of this institute. The institute members are in charge of more than 40 national projects, including some of the most important ones like the national 973 project. The institute members actively cooperate with scientists and academic institutes around the world, including France, Italy, Germany, Japan, USA，UK, and Singapore., also regularly communicate with companies like Microsoft, Intel, Google, IBM, Oracle, Baidu, and Tencent. Some recent research work of the institute members can be found in journals and conferences such as J. ACM, SIAM J. on Comput., TCS, Acta Informatica, Inform. and Comput., LICS, ICALP, SIGCOMM, SIGMOD, KDD, ICDE, STOC, FOCS.
Interaction Theory
Theory of Interaction aims to provide a uniform treatment of both computation models (Church, Turing, …) and interaction models (Milner, Hoare, …). More importantly it offers a model independent approach to completeness theory, equality theory and expressiveness theory for interaction models. It is based upon four foundational principles and two universal relations (absolute equality, subbisimilarity). Using these two relations, Church-Turing Thesis can be formulated as Axiom of Completeness.
