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

[ Group Profile ]

The overall research goal of our group is to understand the power and limitations of computation and to help lay down solid foundations for other areas of computer science. In the following, we briefly describe the research topics that we are currently focusing on.

(1) Quantum cryptography
Quantum cryptography aims to understand the roles of quantum computation in cryptography, which may act as a double-edged sword. On one hand, quantum key distribution (QKD) enables secure communication with information-theoretic security, which is impossible with classical methods. On the other hand, Shor´s quantum algorithm can be used to break many cryptosystems that we use in our daily lives. We are generally interested in investigating the diverse roles of quantum computing in cryptography, some of which have been proposed by us. Topics include device-independent cryptography, securing quantum computation, post-quantum cryptography against quantum side-information (e.g., quantum leakage-resilient cryptography), and new quantum assumptions and tasks.

(2) Geometric Computing
The Voronoi diagram is a versatile geometric construct in geometric computing. Methods for computing the Voroni diagram, as well as its properties and complexity are among the fundamental problems to be studied. By introducing different metrics, such as time-distance, the diagram will change. In general, we are interested in how the properties of the Voronoi diagram vary with each metric and how we can make use of the properties of the underlying metric to efficiently construct the diagram. Furthermore, related problems (such as the time-based shortest route planning, competitive facility location for homogeneous facilities, and cooperative facility location for heterogeneous facilities, etc.), are of both theoretical and practical importance, in diverse areas, including transportation networks, wireless sensor networks, VLSI design, and many others.

(3) Combinatorial Optimization and Approximation Algorithms We consider a series of combinatorial optimization problems related to minimum dominating set and energyefficient scheduling, and the corresponding approximation algorithms. The former includes a natural generalization, which we call the capacitated dominating set problem, which considers capacity and demand constraints of the vertices, and the capacitated facility location problem, which further considers the assignment cost in the objective to be optimized. Both of these problems are among the central issues in the study of approximation algorithms and have received considerable attention with many results in recent years. Study of the latter topic aims to provide energy-efficiency for modern systems from the perspective of algorithm design and analysis. By utilizing mechanisms provided in the hardware level, such as low-power standby modes and dynamic voltage frequency scaling, we seek to develop algorithms with provable energy-efficiency guarantees. Throughout the process of algorithmic research, we aim to develop not only efficient algorithms and suitable approximation solutions, but also fundamental techniques and tools that can be used for a wide range of related problems.
(4) Massive Data
  • Logics for Massive Data: Considerable amounts of information and knowledge are implicit in massive data. We intend to study the problems of knowledge representation and reasoning in data science by using formal logics. With proper representation frameworks and logical formalisms, knowledge discovered from massive data can be used in data-intensive intelligent systems.

  • Efficient Data Intensive Algorithms: With the rapid development of computer and communication technology, it has become much easier to access and store massive amounts of electronic data. We are interested in the research problems concerning efficient computation of massive data, which include efficient epidemic simulation, visualization and construction of disease networks, and classical computer games.

(5) Graph Theory and Algorithms
Foundation: Graphs are used to model many important applications and are the main tool for solving many theoretical problems. We often start by probing fundamental theoretical problems, such as the structures of graphs with certain properties. With these properties, we then design efficient solutions to the problems. We are working on efficient graph algorithms for the streaming model.

(6) Computational Learning Theory
Many situations in daily life require us to make repeated decisions before knowing the outcomes of those decisions. This motivates the study of the online decision problem, in which one must iteratively choose an action and then receive some corresponding loss for a number of rounds. For this problem, we identify natural scenarios, for which we can improve performance of online algorithms. Moreover, we discover new applications of this problem in different areas, such as machine learning, game theory, and complexity theory.

(7) Robotics Path/trajectory planning and navigation of wheeled mobile robots with extension into 3D scenarios, and subject to environment constraints (such as obstacle avoidance) and kinodynamic constraints (such as limits on curvature, velocity and acceleration) are the focus of our work. 3D scenarios include unmanned aerial vehicles, or mobile robots moving on curved terrain with elevation and curvature variations. We developed an obstacle avoidance system based on a boundary value problem of the Laplace equation, which is analagous to fluid flow. The real-time and anytime characteristics of the obstacle avoidance system are verified via mobile robot navigation experiments and numerical simulations using a finite difference method for solving the Laplace equation.