[ 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
(2) Geometric Computing
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
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
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.
(5) Complexity Theory
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.
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.
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
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.