Computation Theory and Algorithms Laboratory

**Principal Investigators:**

Chi-Jen Lu (Chair) | Kai-Min Chung | Tsan-sheng Hsu | Ming-Tat Ko |

Der-Tsai Lee | Churn-Jung Liau | Jing-Sin Liu | Da-Wei Wang |

Bo-Yin Yang |

**[ Group Profile ]**

**(1) Computational Learning Theory**

Many situations in daily life require us to make repeated decisions before knowing the resulting outcomes. This motivates the study of the so-called 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 in which online algorithms with improved performances can be designed. Moreover, we are discovering new applications of this problem in different areas, such as machine learning, game theory, and complexity theory.

**(2) Cryptography**

• Efficient Cryptography and CHES (Crypto Hardware and Embedded Systems): We are working on designing cryptographical approaches for specialized hardware, including implementing cryptographical algorithms in vector units in CPUs, FPGAs, ASICs, and GPU (graphic processing units). One of our record-breaking results is the use of GPUs to assist in 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: Our work on MPKCs (Multivariate Public-Key Cryptosystems) has advanced our 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 that on MPKCs, since an attack on an MPKC is equivalent to solving a multivariate quadratic system (MQ) or the extended isomorphism of polynomials (EIP).

• Theoretical Cryptography: Theoretical cryptography aims to understand the feasibility and limitations of various ambitious cryptographic tasks. Recently, there has been very rapid progress in cryptography, realizing strong primitives that were not even imaginable before. We have participated in this development, proposing new notions of program obfuscations and new constructions of functional encryptions. Additionally, we are identifying and obtaining new desiderata for large-scale multi-party computation, motivated by the explosion in big data available through the Internet. We are also interested in investigating various subjects beyond computer science through a cryptographic lens• casting new light on these topics.

• Quantum Cryptography: A major goal in quantum cryptography is to exploit the power of quantum mechanics to realize cryptographic tasks that are impossible through classical means. We are particularly interested in the field of deviceindependent quantum cryptography, which assumes that the only quantum power comes from untrusted quantum devices that may be prepared by adversaries. This minimizes the trust on quantum operations and hence provides the strongest form of security. We explore tasks achievable in this setting, such as device-independent quantum key distribution (DIQKD) and physical randomness extractors (PRE).

**(3) Massive Data**

• Logic and Knowledge Representation for Massive Data: Considerable amounts of information and knowledge are implicit in massive data. We intend 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 dataintensive computational systems.

• Efficient Data Intensive 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 nterested in the research problems concerning efficient computation of massive data, which include data privacy, issues in large scale social networks, and classical computer games.

**(4) 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 them. We work on algorithmic graph problems that arise 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 diverse areas, such as VLSI design, wireless sensor networks, bioinformatics, and communication networks. With respect to different applications, these issues manifest themselves in different forms, with subtle similarities via various quality measurements and constraints in practice.

• Geometric Computing: The Voronoi diagram is a highly versatile and well-studied geometric construct in geometric computing. The properties, complexity, and computation of the Voronoi diagram are among the fundamental problems under 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 to make use of the properties of the selected metric, if any, to construct the diagram.

**(5) Robotics**

The development of intelligent robotic systems to ensure the safety and comfort of human-robot interactions is of paramount importance for current and near-future robotics research. Ensuring that robots are good partners and helpers for human beings requires the theory and technology for sensing, planning and control, as well as their integration. Within the context of robotics research, we are conducting simulations and experiments on autonomous navigation based on 3D map building, smooth path planning using soft computing, and robot- assisted sensor networks.