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.