Page 40 - profile2012.indd

Research Laboratories 研究群

計算理論與演算法實驗室

Computation Theory

and Algorithms Laboratory

Research Faculty
Research Faculty

Tsan-sheng Hsu Ming-Tat Ko Der-Tsai Lee Churn-Jung Liau Jing-Sin Liu Chi-Jen Lu Da-Wei Wang Bo-Yin Yang
Research Fellow Research Fellow Distinguished Research Fellow Research Fellow Associate Research Fellow Research Fellow Research Fellow Associate Research Fellow

Group Profile
(1) Graph Theory and Algorithms first approach is to study whether or not randomized algorithms can be effi-
ciently converted into deterministic ones. We show how this can be achieved
Fundation: Graphs are used to model many important applica- under reasonable assumptions, and we also study its potential limitation.
tions and are a main tool for solving many theoretical problems. The second approach is to design procedures, called extractors, which can
We often start with probing fundamental theoretical problems extract almost perfect randomness from slightly random sources. We pro-
such as the structure of graphs with certain properties. With vide an optimal construction of extractors, and we also find applications of Computation theory and
these properties, we then design efficient solutions to them. extractors in cryptography.
We work on algorithmic graph problems arisen from real-world algorithms is the foundation
applications. (6) Cryptography of Computer Science with
Network Design and Analysis: The network design problem Efficient Cryptography and CHES (Crypto Hardware and Embedded Systems): studies of power and limits
considers how to connect a collection of sites by a network We are working on designing cryptographical approaches for specialized
such that certain requirements are met. Topics in network de- hardware, including implementing cryptographical algorithms on vector of computing problems.
sign arise as central issues in wide areas, such as VLSI design, units in CPUs, FPGAs, ASICs, and GPU (graphic processing units). One of our
wireless sensor network, bioinformatics, and communication record-breaking results is using GPUs to assist cryptanalytic computations.
networks. With respect to different applications, these issues We also study the implementation of practical information security algo-
demonstrate themselves in different forms, with subtle simi- rithms, such as using intelligent agents to assist server-less authenticated
larities via various quality measurements and constraints in information exchanges.
practice.
mous navigation based on 3D map building, smooth path plan- Post-Quantum Cryptography: We work on MPKCs (Multivariate Public-Key
(2) Geometric Computing ning using soft computing and robot-assisted sensor network. Cryptosystems) that has advanced the understanding of the field from both
theoretical and practical viewpoints. MPKCs operate on a vector of variables
The Voronoi diagram is a very versatile and well-studied geo- (4) Data-Intensive Computation over a small field, instead of on an element in a huge algebraic structure (as
metric construct in geometric computing. The properties, in RSA or ECC). This key characteristic makes MPKCs faster while maintaining
complexity, and computation of Voronoi diagram are among Logic and knowledge representation: Much information and comparable design security; hence, they are useful for low-resource environ-
the fundamental problems to study. By introducing different knowledge are implicit in massive data. Wewant to study the ments, such as embedded systems and smart cards.
metrics, such as time-distance, the diagram will change. In related knowledge representation and reasoning problems
general, we plan to study how the properties of the Voronoi based on formal logics. With a proper representation frame- Algebraic Cryptanalysis: We work on faster implementations and additional
diagram vary with the metric selected, and how we make use work, knowledge discovered from massive data can be used in theory behind such system-solvers. This work also relates to the previously
of the properties of the selected metric, if any, to construct the intelligent data-intensive computational systems. mentioned area above, since an attack on an MPKC is equivalent to solving
diagram. an instance of the multivariate quadratic systems (MQ) or the extended iso-
Efficient algorithms: With the rapid development of computer morphism of polynomials (EIP) problems.
(3) Robtics and communication technology, it has become much easier to
access or store massive amounts of data electronically. We are
The development of intelligent robotic systems to ensure the interested in the research problems concerning efficient com-
safety and comfort of human-robot interaction is of paramount putation of massive data which include data privacy, issues in
importance in current and near future robotics research. To large scale social networks and classical computer games.
make robots as good partner and good helper of human be-
ings requires the theory and technology of sensing, planning (5) Complexity Theory
and control and their integration. Along the line of robotics
research, we conduct simulations and experiments on autono- Randomness has become a valuable resource in computation,
as randomized algorithms have provided the most efficient so-
lutions 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

研究群
40 Research Laboratories
40
41
41