Institute of Information Science
Computation Theory and Algorithms Laboratory
Principal Investigators:
:::Bo-Yin Yang (Chair) :::Tsan-sheng Hsu :::Ming-Tat Ko :::Der-Tsai Lee
:::Churn-Jung Liau :::Jing-Sin Liu :::Chi-Jen Lu :::Da-Wei Wang
:::Kai-Min Chung

[ Group Profile ]

(1) Graph Theory and Algorithms
Fundation: Graphs are used to model many important applications and are a main tool for solving many theoretical problems. We often start with probing fundamental theoretical problems such as the structure of graphs with certain properties. With these properties, we then design efficient solutions to them. We work on algorithmic graph problems arisen from real-world applications.

Network Design and Analysis: The network design problem considers how to connect a collection of sites by a network such that certain requirements are met. Topics in network design arise as central issues in wide areas, such as VLSI design, wireless sensor network, bioinformatics, and communication networks. With respect to different applications, these issues demonstrate themselves in different forms, with subtle similarities via various quality measurements and constraints in practice.
(2) Geometric Computing
The Voronoi diagram is a very versatile and well-studied geometric construct in geometric computing. The properties, complexity, and computation of Voronoi diagram are among the fundamental problems to study. By introducing different metrics, such as time-distance, the diagram will change. In general, we plan to study how the properties of the Voronoi diagram vary with the metric selected, and how we make use of the properties of the selected metric, if any, to construct the diagram.
(3) Robtics
The development of intelligent robotic systems to ensure the safety and comfort of human-robot interaction is of paramount importance in current and near future robotics research. To make robots as good partner and good helper of human beings requires the theory and technology of sensing, planning and control and their integration. Along the line of robotics research, we conduct simulations and experiments on autonomous navigation based on 3D map building, smooth path planning using soft computing and robot-assisted sensor network.
�ƪ�����(4) Data-Intensive Computation
Logic and knowledge representation: Much information and knowledge are implicit in massive data. Wewant to study the related knowledge representation and reasoning problems based on formal logics. With a proper representation framework, knowledge discovered from massive data can be used in intelligent data-intensive computational systems.

Efficient algorithms: With the rapid development of computer and communication technology, it has become much easier to access or store massive amounts of data electronically. We are interested in the research problems concerning efficient computation of massive data which include data privacy, issues in large scale social networks and classical computer games.
(5) Complexity Theory
Randomness has become a valuable resource in computation, as randomized algorithms have provided the most efficient solutions for many important computational problems. However, randomized algorithms typically depend on the availability of a perfect random source, whose existence even in the nature is debatable. There are two approaches to resolve this issue. The first approach is to study whether or not randomized algorithms can be efficiently converted into deterministic ones. We show how this can be achieved under reasonable assumptions, and we also study its potential limitation. The second approach is to design procedures, called extractors, which can extract almost perfect randomness from slightly random sources. We provide an optimal construction of extractors, and we also find applications of extractors in cryptography.
(6) Cryptography
Efficient Cryptography and CHES (Crypto Hardware and Embedded Systems): We are working on designing cryptographical approaches for specialized hardware, including implementing cryptographical algorithms on vector units in CPUs, FPGAs, ASICs, and GPU (graphic processing units). One of our record-breaking results is using GPUs to assist cryptanalytic computations. We also study the implementation of practical information security algorithms, such as using intelligent agents to assist server-less authenticated information exchanges.

Post-Quantum Cryptography: We work on MPKCs (Multivariate Public-Key Cryptosystems) that has advanced the understanding of the field from both theoretical and practical viewpoints. MPKCs operate on a vector of variables over a small field, instead of on an element in a huge algebraic structure (as in RSA or ECC). This key characteristic makes MPKCs faster while maintaining comparable design security; hence, they are useful for low-resource environments, such as embedded systems and smart cards.

Algebraic Cryptanalysis: We work on faster implementations and additional theory behind such system-solvers. This work also relates to the previously mentioned area above, since an attack on an MPKC is equivalent to solving an instance of the multivariate quadratic systems (MQ) or the extended isomorphism of polynomials (EIP) problems.


Academia Sinica Institue of Information Science Academia Sinica