Kyushu University Academic Staff Educational and Research Activities Database
Researcher information (To researchers) Need Help? How to update
Shuji Kijima Last modified date:2018.05.30



Graduate School
Undergraduate School


Homepage
http://tcslab.csce.kyushu-u.ac.jp/~kijima/
Academic Degree
Ph.D.
Field of Specialization
Mathematical Engineering
Outline Activities
Shuji Kijima is interested in Probabilistic Algorithms.
Research
Research Interests
  • Probabilistic Algorithms
    keyword : Randomization, Derandomization
    2010.04~2020.03.
  • Discrete Mathematics
    keyword : Graph theory, Matroid theory, Rigidity theory
    2010.04~2020.03.
Academic Activities
Papers
1. Yukiko Yamauchi, Taichi Uehara, Shuji Kijima, Masafumi Yamashita, Plane formation by synchronous mobile robots in the three-dimensional Euclidean space, Journal of the ACM, https://doi.org/10.1145/3060272, 64, 3, 2017.06, Creating a swarm of mobile computing entities, frequently called robots, agents, or sensor nodes, with self-organization ability is a contemporary challenge in distributed computing. Motivated by this, we investigate the plane formation problem that requires a swarm of robots moving in the three-dimensional Euclidean space to land on a common plane. The robots are fully synchronous and endowed with visual perception. But they do not have identifiers, nor access to the global coordinate system, nor any means of explicit communication with each other. Though there are plenty of results on the agreement problem for robots in the two-dimensional plane, for example, the point formation problem, the pattern formation problem, and so on, this is the first result for robots in the three-dimensional space. This article presents a necessary and sufficient condition for fully synchronous robots to solve the plane formation problem that does not depend on obliviousness, i.e., the availability of local memory at robots. An implication of the result is somewhat counter-intuitive: The robots cannot form a plane from most of the semi-regular polyhedra, while they can form a plane from every regular polyhedron (except a regular icosahedron), whose symmetry is usually considered to be higher than any semi-regular polyhedron..
2. Shuji Kijima, Kentaro Koga, Kazuhisa Makino, Deterministic random walks on finite graphs, Random Structures & Algorithms, 10.1002/rsa.20533, 46, 4, 739-761, 2015.07.
3. Takeharu Shiraga, Yukiko Yamauchi, Shuji Kijima, Masafumi Yamashita, L∞-discrepancy analysis of polynomial-time deterministic samplers emulating rapidly mixing chains, Lecture Notes in Computer Science, 8591, 25-36, 2014.08.
4. Shuji Kijima, Yota Otachi, Toshiki Saitoh, Takeaki Uno, Subgraph isomorphism in graph classes, Discrete Mathematics, 10.1016/j.disc.2012.07.010, 312, 21, 3164--3173, 2012.11.
5. Shuji Kijima and Shin-ichi Tanigawa, Sparsity and connectivity of medial graphs: concerning two edge-disjoint Hamiltonian paths in planar rigidity circuits, Discrete Mathematics, 10.1016/j.disc.2012.04.013, 312, 16, 2466--2472, 2012.08.
6. Shuji Kijima and Toshio Nemoto, On randomized approximation for finding a level ideal of a poset and the generalized median stable matchings, Mathematics of Operations Research, 10.1287/moor.1110.0526, 2012.05.
7. Shota Yasutake, Kohei Hatano, Shuji Kijima, Eiji Takimoto, Masayuki Takeda, Online linear optimization over permutations, Lecture Notes in Computer Science, 10.1007/978-3-642-25591-5_55, 7074, 534--543, 2011.12.
8. Masatora Ogata, Yukiko Yamauchi, Shuji Kijima, Masafumi Yamashita, A randomized algorithm for finding frequent elements in streams using O(loglog N) space, Lecture Notes in Computer Science, 10.1007/978-3-642-25591-5_53, 7074, 514--523, 2011.12.
9. Shuji Kijima and Tomomi Matsui, Polynomial time perfect sampling algorithm for two-rowed contingency tables, Random Structures and Algorithms, 10.1002/rsa.v29:2, 29, 2, 243--256, 2006.09.
Presentations
1. Mizuki Hirakawa, Yukiko Yamauchi, Shuji Kijima, Masafumi Yamashita, On the structure of popular matchings in the stable marriage problem - who can join a popular matching?, The 3rd International Workshop on Matching Under Preferences (MATCH-UP 2015), 2015.04.
Membership in Academic Society
  • The Institute of Electronics, Information and Communication Engineers
  • Japanese Society of Computational Statistics
  • Information Processing Society of Japan
  • Japan Statistical Sciety
  • The Operations Research Society of Japan
Educational
Educational Activities
He focuses on educating algorithm theory, probability theory, discrete mathematics, etc.