1. |
Naoki Kato and Shuji Kijima , On the gap between the rank and the nonnegative rank of a nonnegative matrix, The 21st Japan-Korea Joint Workshop on Algorithms and Computation (WAAC 2018), 2018.08. |

2. |
Junpei Nakashima, Yukiko Yamauchi, Shuji Kijima and Masafumi Yamashita, Finding submodularity hidden in symmetric difference, First Conference on Discrete Optimization and Machine Learning, RIKEN Center for Advanced Intelligence Project, 2018.07. |

3. |
Shuji Kijima, Approximating volume - randomized vs. deterministic, The 10th Japanese-Hungarian Symposium on Discrete Mathematics and Its Applications, 2017.05. |

4. |
Akihiro Monde, Yukiko Yamauchi, Shuji Kijima, Masafumi Yamashita, Localization by an oblivious mobile robot with limited visibility, The 19th Japan-Korea Joint Workshop on Algorithms and Computation (WAAC 2016), 2016.08. |

5. |
Yusaku Tomita, Yukiko Yamauchi, Shuji Kijima, Masafumi Yamashita, Plane Formation by Autonomous Mobile Robots without Chirality, The 19th Japan-Korea Joint Workshop on Algorithms and Computation (WAAC 2016), 2016.08. |

6. |
Yukiko Yamauchi, Taichi Uehara, Shuji Kijima, Masafumi Yamashita, Plane formation by synchronous mobile robots in the three dimensional Euclidean space, The 29th International Symposium on Distributed Computing (DISC 2015), 2015.10. |

7. |
Takeharu Shiraga, Yukiko Yamauchi, Shuji Kijima, Masafumi Yamashita, Total variation discrepancy of deterministic random walks for ergodic Markov chains, 13th Workshop on Analytic Algorithmics and Combinatorics 2016, ANALCO 2016, 2016.01, Motivated by a derandomization of Markov chain Monte Carlo (MCMC), this paper investigates deterministic random walks, which is a deterministic process analogous to a random walk. While there are some progress on the analysis of the vertex-wise discrepancy (i.e., L_{∞} discrepancy), little is known about the total variation discrepancy (i.e., Li discrepancy), which plays a significant role in the analysis of an FPRAS based on MCMC. This paper investigates upper bounds of 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(m√t∗ log t∗) for non-oblivious deterministic random walks, if the corresponding Markov chain is ergodic and lazy. We also present some lower bounds.. |

8. |
Taichi Uehara, Yukiko Yamauchi, Shuji Kijima, Masafumi Yamashita, Forming a plane by semi-synchronous autonomous mobile robots, Workshop on Distributed Robotic Swarms, 2015.10. |

9. |
Kenichi Tamatani, Yukiko Yamauchi, Shuji Kijima, Masafumi Yamashita, On the reconstruction of Laman graphs, Tthe 9th Hungarian-Japanese Symposium on Discrete Mathematics and Its Applications, 2015.06. |

10. |
Ei Ando, Shuji Kijima, An FPTAS for the volume computation of multiply constrained 0-1 knapsack polytopes based on approximate convolution, Tthe 9th Hungarian-Japanese Symposium on Discrete Mathematics and Its Applications, 2015.06. |

11. |
Hiroshi Nishiyama, Yukiko Yamauchi, Shuji Kijima, Masafumi Yamashita, The parity Hamiltonian cycle problem in directed graphs, Tthe 9th Hungarian-Japanese Symposium on Discrete Mathematics and Its Applications, 2015.06. |

12. |
Takeharu Shiraga, Yukiko Yamauchi, Shuji Kijima, Masafumi Yamashita, Deterministic random walks for rapidly mixing chains, Tthe 9th Hungarian-Japanese Symposium on Discrete Mathematics and Its Applications, 2015.06. |

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

14. |
Shuji Kijima, Deterministic random walks on finite graphs, Workshop "Random Walks on Random Graphs and Applications, 2015.04. |

15. |
Ei Ando, Shuji Kijima, An FPTAS for the volume computationof 0-1 knapsack polytopes based on approximate convolution integral, The 25th International Symposium on Algorithms and Computation (ISAAC 2014), 2014.12. |

16. |
Fengqi Chen, Yukiko Yamauchi, Shuji Kijima, Masafumi Yamashita, Locomotion of metamorphic robotic system based on local information (extended abstract), Workshop on Self-organization in Swarm of Robots: from Molecular Robots to Mobile Agents, 2014.10. |

17. |
Takeharu Shiraga, Yukiko Yamauchi, Shuji Kijima, Masafumi Yamashita, An Analysis of Deterministic Random Walks on Hypercubes using the Krawtchouk Polynomial, The 20th Conference of the International Federation of Operational Research Societies (IFORS 2014), 2014.07. |

18. |
Heejae Yim, Yukiko Yamauchi, Shuji Kijima, Masafumi Yamashita, Estimation of Non-linear Function of the Frequency in A Pairwise Data Stream, The 17th Korea-Japan Joint Workshop on Algorithms and Computation (WAAC 2014), 2014.07. |

19. |
Tadahiro Matsukawa, Yukiko Yamauchi, Shuji Kijima, Masafumi Yamashita, On Self-Adjusting Optimal Binary Search Trees, The 17th Korea-Japan Joint Workshop on Algorithms and Computation (WAAC 2014), 2014.07. |

20. |
Takumi Yone, Yukiko Yamauchi, Shuji Kijima, Masafumi Yamashita, Assignment of edge lengths in an approximate tree metric, The 17th Korea-Japan Joint Workshop on Algorithms and Computation (WAAC 2014), 2014.07. |

21. |
Takeharu Shiraga, Yukiko Yamauchi, Shuji Kijima, Masafumi Yamashita, L_{∞}-Discrepancy analysis of polynomial-time deterministic samplers emulating rapidly mixing chains, 20th International Computing and Combinatorics Conference, COCOON 2014, 2014.01, Markov chain Monte Carlo (MCMC) is a standard technique to sample from a target distribution by simulating Markov chains. In an analogous fashion to MCMC, this paper proposes a deterministic sampling algorithm based on deterministic random walk, such as the rotor-router model (a.k.a. Propp machine). For the algorithm, we give an upper bound of the point-wise distance (i.e., infinity norm) between the "distributions" of a deterministic random walk and its corresponding Markov chain in terms of the mixing time of the Markov chain. As a result, for uniform sampling of #P-complete problems, such as 0-1 knapsack solutions, linear extensions, matchings, etc., for which rapidly mixing chains are known, our deterministic algorithm provides samples with a "distribution" with a point-wise distance at most ε from the target distribution, in time polynomial in the input size and ε^{-1}.. |

22. |
Kohei Kubo, Yukiko Yamauchi, Shuji Kijima, Masafumi Yamashita, On approximation of normalized compression distance by tree metric for clustering, The 16th Korea-Japan Joint Workshop on Algorithms and Computation (WAAC 2013), 2013.06. |

23. |
Heejae Yim, Norikazu Takahashi, Yukiko Yamauchi, Shuji Kijima, Masafumi Yamashita, Finding items associated with varied members in a pairwise data stream, The 16th Korea-Japan Joint Workshop on Algorithms and Computation (WAAC 2013), 2013.06. |

24. |
Hiroshi Nishiyama, Yukiko Yamauchi, Shuji Kijima, Masafumi Yamashita, Parity longest cycle problem, The 16th Korea-Japan Joint Workshop on Algorithms and Computation (WAAC 2013), 2013.06. |

25. |
Mizuki Hirakawa, Yukiko Yamauchi, Shuji Kijima, Masafumi Yamashita, Any max-cardinality popular matching in a stable marriage problem consists of the same people, The 8th Japanese-Hungarian Symposium on Discrete Mathematics and Its Applications, 2013.06. |

26. |
Naoto Sonoda, Yukiko Yamauchi, Shuji Kijima, Masafumi Yamashita, A randomized streaming algorithm for finding distinction of frequent items in distributed systems, The 8th Japanese-Hungarian Symposium on Discrete Mathematics and Its Applications, 2013.06. |

27. |
Shuji Kijima, Randomness in Algorithm Design, ELC Workshop on Randomness and Probability Through Computability (RPTC2013), 2013.05. |

28. |
Shuji Kijima, Deterministic random walk on finite graphs, Markov Chains on Graphs and Related Topics, 2013.02. |

29. |
Kosuke Koba, Yukiko Yamauchi, Shuji Kijima, Masafumi Yamashita, Hitting time and cover time on dynamic graphs, The 36th Australasian Conference on Combinatorial Mathematics and Combinatorial Computing (ACCMCC), 2012.12. |

30. |
Yusuke Hosaka, Yukiko Yamauchi, Shuji Kijima, Masafumi Yamashita, Fast random walk and its stationary distribution, The 36th Australasian Conference on Combinatorial Mathematics and Combinatorial Computing (ACCMCC), 2012.12. |

31. |
Yukiko Yamauchi, Sebastien Tixeuil, Shuji Kijima, Masafumi Yamashita, Brief announcement: Probabilistic stabilization under probabilistic schedulers, The 26th International Symposium on Distributed Computing (DISC 2012), 2012.10. |

32. |
Shuji Kijima, Efficient randomized rounding in permutahedron, 21st International Symposium on Mathematical Programming (ISMP 2012), 2012.08. |

33. |
Yusuke Hosaka, Yukiko Yamauchi, Hirotaka Ono, Shuji Kijima, Masafumi Yamashita, An extension of Matthews' bound to multiplex random walks, The 14th Workshop on Advances in Parallel and Distributed Computational Models (APDCM 2012), 2012.05. |

34. |
Shuji Kijima, Kentaro Koga, Kazuhisa Makino, Deterministic random walks on finite graphs, Analytic Algorithmics and Combinatorics (ANALCO 2012), 2012.01. |

35. |
Shuji Kijima, Probability and computation, 2011.12. |

36. |
Yusuke Hosaka, Shuji Kijima, Masafumi Yamashita, On cover time of multiplex random walks, The 14th Korea-Japan Joint Workshop on Algorithms and Computation (WAAC 2011), 2011.07. |

37. |
Kosuke Koba, Shuji Kijima, Masafumi Yamashita, Random walks on dynamic graphs, The 14th Korea-Japan Joint Workshop on Algorithms and Computation (WAAC 2011), 2011.07. |

38. |
Yuji Mihara, Shuji Kijima, Masafumi Yamashita, On random maze via Markov chain Monte Carlo, The 14th Korea-Japan Joint Workshop on Algorithms and Computation (WAAC 2011), 2011.07. |

39. |
Shota Yasutake, Kohei Hatano, Shuji Kijima, Eiji Takimoto, Masayuki Takeda, Online prediction over permutahedron, The 14th Korea-Japan Joint Workshop on Algorithms and Computation (WAAC 2011), 2011.07. |

40. |
Shuji Kijima, Yota Otachi, Toshiki Saitoh, Takeaki Uno, Subgraph isomorphism in graph classes, The 14th Korea-Japan Joint Workshop on Algorithms and Computation (WAAC 2011), 2011.07. |

41. |
Yota Otachi, Toshiki Saitoh, Katsuhisa Yamanaka, Shuji Kijima, Yoshio Okamoto, Hirotaka Ono, Yushi Uno, Koichi Yamazaki, Approximability of the Path-Distance-Width for AT-free Graphs, The 37th International Workshop on Graph-Theoritic Concepts in Computer Science (WG 2011), 2011.06. |

42. |
Shuji Kijima, Sampling from log-super/submodular distributions, The 7th Hungarian-Japanese Symposium on Discrete Mathematics and Its Applications, 2011.06. |

43. |
Ryu Mizoguchi, Hirotaka Ono, Shuji Kijima, Masafumi Yamashita, Upper and lower bounds of space complexity of self-stabilizing leader election in mediated population protocol, The 14th International Conference On Principles Of Distributed Systems (OPODIS 2010), 2010.12. |

44. |
Ryo Nakatsubo, Shuji Kijima, Tomomi Matsui, Computational experiments of perfect sampling algorithms for two-way contingency tables, International Conference OPERATIONS RESEARCH (MUNICH 2010), 2010.09. |

45. |
Shuji Kijima, Yoshio Okamoto, Takeaki Uno, Counting the number of dominating sets in graph classes, The 13th Japan-Korea Joint Workshop on Algorithms and Computation (WAAC 2010), 2010.07. |

46. |
Ryo Nakatsubo, Shuji Kijima, Tomomi Matsui, Computational experiments on perfect sampling of contingency tables, The 3rd Annual Meeting of the Asian Association for Algorithms and Computation (AAAC 2010), 2010.04. |