1. |
Tianxiang He, Chansu Han, Ryoichi Isawa, Takeshi Takahashi, Shuji Kijima, Jun’ichi Takeuchi, Koji Nakao, A fast algorithm for constructing phylogenetic trees with application to IoT malware clustering, *26th International Conference on Neural Information Processing, ICONIP 2019
Neural Information Processing - 26th International Conference, ICONIP 2019, Proceedings*, 10.1007/978-3-030-36708-4_63, 766-778, 2019.12, For efficiently handling thousands of malware specimens, we aim to quickly and automatically categorize those into malware families. A solution for this could be the neighbor-joining method using NCD (Normalized Compression Distance) as similarity of malware. It creates a phylogenetic tree of malware based on the NCDs between malware binaries for clustering. However, it is frustratingly slow because it requires (N^{2}+N)/2 compression attempts for the NCDs, where N is the number of given specimens. For fast clustering, this paper presents an algorithm for efficiently constructing a phylogenetic tree by greatly reducing compression attempts. The key idea to do so is not to construct a tree of N specimens all at once. Instead, it divides N specimens into temporal clusters in advance, constructs a small tree for each temporal cluster, and joins the trees as a united tree. Intuitively, separately constructing small trees requires a much smaller number of compression attempts than (N^{2}+N)/2. With experiments using 4,109 in-the-wild malware specimens, we confirm that our algorithm achieved clustering 22 times faster than the neighbor-joining method with a good accuracy of 97%.. |

2. |
Leszek Gąsieniec, Shuji Kijima, Jie Min, Searching with increasing speeds, *20th International Symposium on Stabilization, Safety, and Security of Distributed Systems, SSS 2018
Stabilization, Safety, and Security of Distributed Systems - 20th International Symposium, SSS 2018, Proceedings*, 10.1007/978-3-030-03232-6_9, 126-138, 2018.01, In the classical search problem on the line or in higher dimension one is asked to find the shortest (and often the fastest) route to be adopted by a robot R from the starting point s towards the target point t located at unknown location and distance D. It is usually assumed that robot R moves with a fixed unit speed 1. It is well known that one can adopt a “zig-zag” strategy based on the exponential expansion, which allows to reach the target located on the line in time ≤9D and this bound is tight. The problem was also studied in two dimensions where the competitive factor is known to be O(D). In this paper we study an alteration of the search problem in which robot R starts moving with the initial speed 1. However, during search it can encounter a point or a sequence of points enabling faster and faster movement. The main goal is to adopt the route which allows R to reach the target t as quickly as possible. We study two variants of the considered search problem: (1) with the global knowledge and (2) with the local knowledge. In variant (1) robot R knows a priori the location of all intermediate points as well as their expulsion speeds. In this variant we study the complexity of computing optimal search trajectories. In variant (2) the relevant information about points in P is acquired by R gradually, i.e., while moving along the adopted trajectory. Here the focus is on the competitive factor of the solution, i.e., the ratio between the solutions computed in variants (2) and (1). We also consider two types of search spaces with points distributed on the line and subsequently with points distributed in two-dimensional space.. |

3. |
Keisuke Doi, Yukiko Yamauchi, Shuji Kijima, Masafumi Yamashita, Exploration of finite 2D square grid by a metamorphic robotic system, *20th International Symposium on Stabilization, Safety, and Security of Distributed Systems, SSS 2018
Stabilization, Safety, and Security of Distributed Systems - 20th International Symposium, SSS 2018, Proceedings*, 10.1007/978-3-030-03232-6_7, 96-110, 2018.01, We consider exploration of a finite 2D square grid by a metamorphic robotic system consisting of anonymous oblivious modules. The number of possible shapes of the metamorphic robotic system grows as the number of modules increases. The shapes of the system serve as its memory and show its functionality. We consider the effect of global compass on the minimum number of modules for exploration of a finite 2D square grid. We show that if the modules agree on the directions (north, south, east, and west), three modules are necessary and sufficient for exploration from an arbitrary initial configuration, otherwise five modules are necessary and sufficient for limited initial configurations.. |

4. |
Takeharu Shiraga, Yukiko Yamauchi, Shuji Kijima, Masafumi Yamashita, Deterministic random walks for rapidly mixing chains, *SIAM Journal on Discrete Mathematics*, 10.1137/16M1087667, 32, 3, 2180-2193, 2018.01, The rotor-router model is a deterministic process analogous to a simple random walk on a graph, and the discrepancy of token configurations between the rotor-router model and its corresponding random walk has been investigated in some contexts. Motivated by general Markov chains beyond simple random walks, this paper investigates a generalized model which imitates a Markov chain (of multiple tokens) possibly containing irrational transition probabilities. We are concerned with the vertexwise discrepancy of the numbers of tokens between the generalized model and its corresponding Markov chain, and present an upper bound of the discrepancy in terms of the mixing time of the Markov chain.. |

5. |
Takahiro Fujita, kohei hatano, Shuji Kijima, Eiji Takimoto, Online combinatorial optimization with multiple projections and its application to scheduling problem, *IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences*, 10.1587/transfun.E101.A.1334, E101A, 9, 1334-1343, 2018.09, We consider combinatorial online prediction problems and propose a new construction method of efficient algorithms for the problems. One of the previous approaches to the problem is to apply online prediction method, in which two external procedures the projection and the metarounding are assumed to be implemented. In this work, we generalize the projection to multiple projections. As an application of our framework, we show an algorithm for an online job scheduling problem with a single machine with precedence constraints.. |

6. |
Zhiqiang Liu, Yukiko Yamauchi, Shuji Kijima, Masafumi Yamashita, Team assembling problem for asynchronous heterogeneous mobile robots, *Theoretical Computer Science*, 10.1016/j.tcs.2018.01.009, 721, 27-41, 2018.04, We investigate the team assembling problem for a swarm of heterogeneous mobile robots which requires the robots to autonomously partition themselves into teams satisfying a given specification A=(a_{1},a_{2},…,a_{k}), where a_{i} is the number of robots with color (i.e., robot type) i in one team. A robot, which is represented by a point in the two-dimensional Euclidean space, is asynchronous, oblivious, and anonymous in the sense that robots with the same color are indistinguishable and all robots execute the same algorithm to determine their moves. It has neither any access to the global coordinate system nor any explicit communication medium. We show that GCD(a_{1},a_{2},…,a_{k})=1 is a necessary and sufficient condition for the robots to have an algorithm to solve the team assembling problem in a self-stabilizing manner, i.e., starting from any arbitrary initial configuration, the robots form teams according to the specification.. |

7. |
Yusaku Tomita, Yukiko Yamauchi, Shuji Kijima, Masafumi Yamashita, Plane formation by synchronous mobile robots without chirality, *21st International Conference on Principles of Distributed Systems, OPODIS 2017
21st International Conference on Principles of Distributed Systems, OPODIS 2017*, 10.4230/LIPIcs.OPODIS.2017.13, 95, 2018.03, We consider a distributed system consisting of autonomous mobile computing entities called robots moving in the three-dimensional space (3D-space). The robots are anonymous, oblivious, fully-synchronous and have neither any access to the global coordinate system nor any explicit communication medium. Each robot cooperates with other robots by observing the positions of other robots in its local coordinate system. One of the most fundamental agreement problems in 3D-space is the plane formation problem that requires the robots to land on a common plane, that is not predefined. This problem is not always solvable because of the impossibility of symmetry breaking. While existing results assume that the robots agree on the handedness of their local coordinate systems, we remove the assumption and consider the robots without chirality. The robots without chirality can never break the symmetry consisting of rotation symmetry and reflection symmetry. Such symmetry in 3D-space is fully described by 17 symmetry types each of which forms a group. We extend the notion of symmetricity [Suzuki and Yamashita, SIAM J. Compt. 1999] [Yamauchi et al., PODC 2016] to cover these 17 symmetry groups. Then we give a characterization of initial configurations from which the fully-synchronous robots without chirality can form a plane in terms of symmetricity.. |

8. |
Hiroshi Nishiyama, Yusuke Kobayashi, Yukiko Yamauchi, Shuji Kijima, Masafumi Yamashita, The parity Hamiltonian cycle problem, *Discrete Mathematics*, 10.1016/j.disc.2017.10.025, 341, 3, 606-626, 2018.03, Motivated by a relaxed notion of the celebrated Hamiltonian cycle, this paper investigates its variant, parity Hamiltonian cycle (PHC): A PHC of a graph is a closed walk which visits every vertex an odd number of times, where we remark that the walk may use an edge more than once. First, we give a complete characterization of the graphs which have PHCs, and give a linear time algorithm to find a PHC, in which every edge appears at most four times, in fact. In contrast, we show that finding a PHC is NP-hard if a closed walk is allowed to use each edge at most z times for each z=1,2,3 (PHC_{z} for short), even when a given graph is two-edge-connected. We then further investigate the PHC_{3} problem, and show that the problem is in P when an input graph is four-edge-connected. Finally, we are concerned with three (or two)-edge-connected graphs, and show that the PHC_{3} problem is in P for any C_{≥5}-free or P_{6}-free graphs. Note that the Hamiltonian cycle problem is known to be NP-hard for those graph classes.. |

9. |
Takeharu Shiraga, Yukiko Yamauchi, Shuji Kijima, Masafumi Yamashita, Total variation discrepancy of deterministic random walks for ergodic Markov chains, *Theoretical Computer Science*, 10.1016/j.tcs.2016.11.017, 699, 63-74, 2017.11, Motivated by a derandomization of Markov chain Monte Carlo (MCMC), this paper investigates a deterministic random walk, which is a deterministic process analogous to a random walk. There is some recent progress in the analysis of the vertex-wise discrepancy (i.e., L_{∞}-discrepancy), while little is known about the total variation discrepancy (i.e., L_{1}-discrepancy), which plays an important role in the analysis of an FPRAS based on MCMC. This paper investigates the L_{1}-discrepancy between the expected number of tokens in a Markov chain and the number of tokens in its corresponding deterministic random walk. First, we give a simple but nontrivial upper bound O(mt^{⁎}) of the L_{1}-discrepancy for any ergodic Markov chains, where m is the number of edges of the transition diagram and t^{⁎} is the mixing time of the Markov chain. Then, we give a better upper bound O(mt^{⁎}) for non-oblivious deterministic random walks, if the corresponding Markov chain is ergodic and lazy. We also present some lower bounds.. |

10. |
Yukiko Yamauchi, Taichi Uehara, Shuji Kijima, Masafumi Yamashita, Plane formation by synchronous mobile robots in the three-dimensional Euclidean space, *Journal of the ACM*, 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.. |

11. |
Ei Ando, Shuji Kijima, An FPTAS for the Volume of Some v-polytopes—It is Hard to Compute the Volume of the Intersection of Two Cross-Polytopes, *23rd International Conference on Computing and Combinatorics, COCOON 2017
Computing and Combinatorics - 23rd International Conference, COCOON 2017, Proceedings*, 10.1007/978-3-319-62389-4_2, 10392 LNCS, 13-24, 2017.01, Given an n-dimensional convex body by a membership oracle in general, it is known that any polynomial-time deterministic algorithm cannot approximate its volume within ratio. There is a substantial progress on randomized approximation such as Markov chain Monte Carlo for a high-dimensional volume, and for many #P-hard problems, while only a few #P-hard problems are known to yield deterministic approximation. Motivated by the problem of deterministically approximating the volume of a -polytope, that is a polytope with a small number of vertices and (possibly) exponentially many facets, this paper investigates the problem of computing the volume of a “knapsack dual polytope,” which is known to be #P-hard due to Khachiyan (1989). We reduce an approximate volume of a knapsack dual polytope to that of the intersection of two cross-polytopes, and give FPTASs for those volume computations. Interestingly, computing the volume of the intersection of two cross-polytopes (i.e.,-balls) is #P-hard, unlike the cases of-balls or -balls.. |

12. |
Akihiro Monde, Yukiko Yamauchi, Shuji Kijima, Masafumi Yamashita, Self-stabilizing localization of the middle point of a line segment by an oblivious robot with limited visibility, *19th International Symposium on Stabilization, Safety, and Security of Distributed Systems, SSS 2017
Stabilization, Safety, and Security of Distributed Systems - 19th International Symposium, SSS 2017, Proceedings*, 10.1007/978-3-319-69084-1_12, 10616 LNCS, 172-186, 2017, This paper poses a question about a simple localization problem, which is arisen from self-stabilizing location problems by oblivious mobile autonomous robots with limited visibility. The question is if an oblivious mobile robot on a line-segment can localize the middle point of the line-segment in finite steps observing the direction (i.e., Left or Right) and distance to the nearest end point. This problem is also akin to (a continuous version of) binary search, and could be closely related to computable real functions. Contrary to appearances, it is far from trivial if this simple problem is solvable or not, and unsettled yet. This paper is concerned with three variants of the original problem, minimally relaxing, and presents self-stabilizing algorithms for them. We also show an easy impossibility theorem for bilaterally symmetric algorithms.. |

13. |
Taichi Uehara, Yukiko Yamauchi, Shuji Kijima, Masafumi Yamashita, Plane formation by semi-synchronous robots in the three dimensional Euclidean space, *Lecture Notes in Computer Science*, 10.1007/978-3-319-49259-9_30, 10083, 383-398, 2016.12. |

14. |
Takahiro Yakami, Yukiko Yamauchi, Shuji Kijima, Masafumi Yamashita, Searching for an evader in an unknown graph by an optimal number of searchers, *Lecture Notes in Computer Science*, 10.1007/978-3-319-49259-9_31, 10083, 399-414, 2016.12. |

15. |
Ei Ando, Shuji Kijima, An FPTAS for the Volume Computation of 0-1 Knapsack Polytopes Based on Approximate Convolution, *Algorithmica*, 10.1007/s00453-015-0096-5, 76, 4, 1245-1263, 2016.12, Computing high dimensional volumes is a hard problem, even for approximation. Several randomized approximation techniques for #P-hard problems have been developed in the three decades, while some deterministic approximation algorithms are recently developed only for a few #P-hard problems. Motivated by a new technique for a deterministic approximation, this paper is concerned with the volume computation of 0-1 knapsack polytopes, which is known to be #P-hard. This paper presents a new technique based on approximate convolutions for a deterministic approximation of volume computations, and provides a fully polynomial-time approximation scheme for the volume computation of 0-1 knapsack polytopes. We also give an extension of the result to multi-constrained knapsack polytopes with a constant number of constraints.. |

16. |
Hiroshi Nishiyama, Yukiko Yamauchi, Shuji Kijima, Masafumi Yamashita, The parity Hamiltonian cycle problem in directed graphs, *Lecture Notes in Computer Science*, 10.1007/978-3-319-45587-7_5, 9849, 92-106, 2016.09. |

17. |
Satoru Iwata, Naoyuki Kamiyama, Naoki Katoh, Shuji Kijima, Yoshio Okamoto, Extended formulations for sparsity matroids, *Mathematical Programming*, 10.1007/s10107-015-0936-8, 158, 1-2, 568-574, 2016.06. |

18. |
Takahiro Fujita, Kohei Hatano, Shuji Kijima, Eiji Takimoto, Online linear optimization for job scheduling under precedence constraints, *Lecture Notes in Computer Science*, 10.1007/978-3-319-24486-0_22, 9355, 332-346, 2015.10. |

19. |
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. |

20. |
Nao Fujinaga, Yukiko Yamauchi, Hirotaka Ono, Shuji Kijima, Masafumi Yamashita, Pattern formation by oblivious asynchronous mobile robots, *SIAM Journal on Computing*, 0.1137/140958682, 44, 3, 740-785, 2015.07. |

21. |
Shuji Kijima, Ravi Montenegro, Collision of random walks and a refined analysis of attacks on the discrete logarithm problem, *Lecture Notes in Computer Science*, 9020, 127-149, 2015.03. |

22. |
Yota Otachi, Toshiki Saitoh, Katsuhisa Yamanaka, Shuji Kijima, Yoshio Okamoto, Hirotaka Ono, Yushi Uno, Koichi Yamazaki, Approximating the path-distance-width for AT-free graphs and graphs in related classes, *Discrete Applied Mathematics*, 168, 69-77, 2014.05. |

23. |
Toru Sasaki, Yukiko Yamauchi, Shuji Kijima, Masafumi Yamashita, Mobile Byzantine agreement on arbitrary network, *Lecture Notes in Computer Science*, 10.1007/978-3-319-03850-6_17, 8304, 236-250, 2013.12. |

24. |
Xiaoguang Xu, Yukiko Yamauchi, Shuji Kijima, Masafumi Yamashita, Space complexity of self-stabilizing leader election in population protocol based on k-interaction, *Lecture Notes in Computer Science*, 10.1007/978-3-319-03089-0_7, 8255, 86-97, 2013.10. |

25. |
Ryu Mizoguchi, Hirotaka Ono, Shuji Kijima, Masafumi Yamashita, On space complexity of self-stabilizing leader election in mediated population protocol, *Distributed Computing*, 25, 6, 451-460, 2012.12. |

26. |
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. |

27. |
Daiki Suehiro, Kohei Hatano, Shuji Kijima, Eiji Takimoto, Kiyohito Nagano, Online prediction under submodular constraints, *Lecture Notes in Computer Science*, 10.1007/978-3-642-34106-9_22, 7568, 260-274, 2012.10. |

28. |
Nao Fujinaga, Yukiko Yamauchi, Shuji Kijima, Masafumi Yamashita, Asynchronous pattern formation by anonymous oblivious mobile robots, *Lecture Notes in Computer Science*, 10.1007/978-3-642-33651-5_22, 7611, 312-325, 2012.10. |

29. |
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. |

30. |
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. |

31. |
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. |

32. |
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. |

33. |
Shuji Kijima, Yoshio Okamoto, Takeaki Uno, Dominating set counting in graph classes, *Lecture Notes in Computer Science*, 10.1007/978-3-642-22685-4_2, 6842, 13--24, 2011.08. |

34. |
Yoshiaki Nonaka, Hirotaka Ono, Shuji Kijima, Masafumi Yamashita, , How slow, or fast, are standard random walks? ---analysis of hitting and cover times on tree, *CRPIT*, 119, 63--68, 2011.01. |

35. |
Nao Fujinaga, Hirotaka Ono, Shuji Kijima, Masafumi Yamashita, , Pattern formation through optimum matching by CORDA oblivious robots, *Lecture Notes in Computer Science*, 10.1007/978-3-642-17653-1_1, 6490, 1--15, 2010.12. |

36. |
Masaki Yamamoto, Shuji Kijima, Yasuko Matsui, A polynomial-time perfect sampler for the Q-Ising with a vertex-independent noise, *Journal of Combinatorial Optimization*, 10.1007/s10878-010-9309-7, 22, 3, 392--408, 2010.09. |

37. |
Tomomi Matsui, Mitsuo Motoki, Naoyuki Kamatani, and Shuji Kijima, Polynomial time approximate or perfect samplers for discretized Dirichlet distribution, *Japan Journal of Industrial and Applied Mathematics*, 10.1007/s13160-010-0002-0, 27, 1, 91--123, 2010.07. |

38. |
Shuji Kijima, Masashi Kiyomi, Yoshio Okamoto, and Takeaki Uno, On listing, sampling, and counting the chordal graphs with edge constraints, *Theoretical Computer Science*, 10.1016/j.tcs.2010.03.024, 411, 26--28, 2591--2601, 2010.03. |

39. |
Shuji Kijima and Tomomi Matsui, Randomized approximation scheme and perfect sampler for closed Jackson networks with multiple servers, *Annals of Operations Research*, 10.1007/s10479-008-0317-2, 162, 35--55, 2008.09. |

40. |
Shuji Kijima and Tomomi Matsui, Approximation algorithm and perfect sampler for closed Jackson networks with single servers, *SIAM Journal on Computing*, 10.1137/06064980X, 38, 4, 1484--1503, 2008.08. |

41. |
Shuji Kijima and Tomomi Matsui, Rapidly mixing chain and perfect sampler for logarithmic separable concave distributions on simplex, *DMTCS Proceedings Series*, AD, 371--382, 2005.07. |

42. |
Masashi Kiyomi, Shuji Kijima, and Takeaki Uno, Listing chordal graphs and interval graphs, *Lecture Notes in Computer Science*, 4271, 68--77, 2006.06. |

43. |
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. |

44. |
Tomomi Matsui and Shuji Kijima, Polynomial time perfect sampler for discretized Dirichlet distribution, 10.1007/978-4-431-75232-5_13, Hiroe Tsubaki, Ken Nishina, and Shu Yamada (eds.), The Grammar of Technology Development, Springer, 2007, 179--199. , 2008.01. |

45. |
Shuji Kijima and Tomomi Matsui, , Approximate counting scheme for mxn contingency tables, *IEICE Transactions on Information and Systems*, E87-D, 308--314, 2004.02. |