Page 42 - 2017 Brochure
P. 42
earch Laboratories
Computation Theory and Algorithms Group Lab
The overall research goal of our group is to understand the Furthermore, related problems (such as the time-based
power and limitations of computation and to help lay down shortest route planning, competitive facility location for
solid foundations for other areas of computer science. In homogeneous facilities, and cooperative facility location
the following, we briefly describe the research topics that we for heterogeneous facilities, etc.), are of both theoretical
are currently focusing on. and practical importance, in diverse areas, including
transportation networks, wireless sensor networks, VLSI
1. Quantum cryptography design, and many others.
Quantum cryptography aims to understand the roles of 3. Combinatorial Optimization and
quantum computation in cryptography, which may act Approximation Algorithms
as a double-edged sword. On one hand, quantum key
distribution (QKD) enables secure communication with We consider a series of combinatorial optimization
information-theoretic security, which is impossible with problems related to minimum dominating set and energy-
classical methods. On the other hand, Shor´s quantum efficient scheduling, and the corresponding approximation
algorithm can be used to break many cryptosystems that algorithms. The former includes a natural generalization,
we use in our daily lives. We are generally interested in which we call the capacitated dominating set problem,
investigating the diverse roles of quantum computing in which considers capacity and demand constraints of the
cryptography, some of which have been proposed by us. vertices, and the capacitated facility location problem,
Topics include device-independent cryptography, securing which further considers the assignment cost in the objective
quantum computation, post-quantum cryptography against to be optimized. Both of these problems are among the
quantum side-information (e.g., quantum leakage-resilient central issues in the study of approximation algorithms and
cryptography), and new quantum assumptions and tasks. have received considerable attention with many results
in recent years. Study of the latter topic aims to provide
2. Geometric Computing energy-efficiency for modern systems from the perspective
of algorithm design and analysis. By utilizing mechanisms
The Voronoi diagram is a versatile geometric construct in provided in the hardware level, such as low-power standby
geometric computing. Methods for computing the Voroni modes and dynamic voltage frequency scaling, we seek
diagram, as well as its properties and complexity are among to develop algorithms with provable energy-efficiency
the fundamental problems to be studied. By introducing guarantees. Throughout the process of algorithmic
different metrics, such as time-distance, the diagram will research, we aim to develop not only efficient algorithms
change. In general, we are interested in how the properties and suitable approximation solutions, but also fundamental
of the Voronoi diagram vary with each metric and how we techniques and tools that can be used for a wide range of
can make use of the properties of the underlying metric to related problems.
efficiently construct the diagram.
40 研究群 Research Laboratories
Computation Theory and Algorithms Group Lab
The overall research goal of our group is to understand the Furthermore, related problems (such as the time-based
power and limitations of computation and to help lay down shortest route planning, competitive facility location for
solid foundations for other areas of computer science. In homogeneous facilities, and cooperative facility location
the following, we briefly describe the research topics that we for heterogeneous facilities, etc.), are of both theoretical
are currently focusing on. and practical importance, in diverse areas, including
transportation networks, wireless sensor networks, VLSI
1. Quantum cryptography design, and many others.
Quantum cryptography aims to understand the roles of 3. Combinatorial Optimization and
quantum computation in cryptography, which may act Approximation Algorithms
as a double-edged sword. On one hand, quantum key
distribution (QKD) enables secure communication with We consider a series of combinatorial optimization
information-theoretic security, which is impossible with problems related to minimum dominating set and energy-
classical methods. On the other hand, Shor´s quantum efficient scheduling, and the corresponding approximation
algorithm can be used to break many cryptosystems that algorithms. The former includes a natural generalization,
we use in our daily lives. We are generally interested in which we call the capacitated dominating set problem,
investigating the diverse roles of quantum computing in which considers capacity and demand constraints of the
cryptography, some of which have been proposed by us. vertices, and the capacitated facility location problem,
Topics include device-independent cryptography, securing which further considers the assignment cost in the objective
quantum computation, post-quantum cryptography against to be optimized. Both of these problems are among the
quantum side-information (e.g., quantum leakage-resilient central issues in the study of approximation algorithms and
cryptography), and new quantum assumptions and tasks. have received considerable attention with many results
in recent years. Study of the latter topic aims to provide
2. Geometric Computing energy-efficiency for modern systems from the perspective
of algorithm design and analysis. By utilizing mechanisms
The Voronoi diagram is a versatile geometric construct in provided in the hardware level, such as low-power standby
geometric computing. Methods for computing the Voroni modes and dynamic voltage frequency scaling, we seek
diagram, as well as its properties and complexity are among to develop algorithms with provable energy-efficiency
the fundamental problems to be studied. By introducing guarantees. Throughout the process of algorithmic
different metrics, such as time-distance, the diagram will research, we aim to develop not only efficient algorithms
change. In general, we are interested in how the properties and suitable approximation solutions, but also fundamental
of the Voronoi diagram vary with each metric and how we techniques and tools that can be used for a wide range of
can make use of the properties of the underlying metric to related problems.
efficiently construct the diagram.
40 研究群 Research Laboratories
