Chuzo Iwamoto

Last Updated :2025/05/09

Affiliations, Positions
Graduate School of Advanced Science and Engineering, Professor
Web Site
https://home.hiroshima-u.ac.jp/chuzo/
E-mail
chuzohiroshima-u.ac.jp
Self-introduction
Chuzo Iwamoto received his B.Eng. degree from Yamaguchi University in 1990, and M.Eng. and Dr. Eng. degrees from Kyushu University in 1992 and 1995, respectively. From 1995 to 1997, he was a lecturer at Kyushu Institute of Design. From 1997 to 2014, he was an associate professor of the Graduate School of Engineering, Hiroshima University. Since 2014, he has been a professor of the Graduate School of Engineering, Hiroshima University. His present interests include computational complexity and automata theory.

Basic Information

Major Professional Backgrounds

  • 1993/04/01, 1995/03/31, Japan Society for the Promotion of Science, Special Postdoctoral Researcher
  • 1995/04/01, 1995/10/31, Kyushu University, Research Associate
  • 1995/11/01, 1997/09/30, Kyushu Institute of Design, Faculty of Design, Lecturer
  • 1997/10/01, 2001/03/31, Hiroshima University, Faculty of Engineering, Associate Professor
  • 2001/04/01, 2007/03/31, Hiroshima University, Graduate School of Engineering, Associate Professor
  • 2007/04/01, 2014/08/31, Hiroshima University, Graduate School of Engineering, Associate Professor
  • 2014/09/01, 2020/03/31, Hiroshima University, Graduate School of Engineering, Professor
  • 2020/04/01, Hiroshima University, Graduate School of Advanced Science and Engineering, Professor

Educational Backgrounds

  • Kyushu University, Graduate School, Division of Engineering, Department of Computer Science and Communication Engineering, Japan, 1990/04, 1995/03
  • Yamaguchi University, Faculty of Engineering, Japan, 1986/04, 1990/03

Academic Degrees

  • Doctor of Engineering, Kyushu University

Educational Activity

  • [Bachelor Degree Program] School of Informatics and Data Science : Department of Informatics and Data Science : Computer Science Program
  • [Master's Program] Graduate School of Advanced Science and Engineering : Division of Advanced Science and Engineering : Informatics and Data Science Program
  • [Doctoral Program] Graduate School of Advanced Science and Engineering : Division of Advanced Science and Engineering : Informatics and Data Science Program

Research Fields

  • Informatics;Principles of Informatics;Theory of informatics

Research Keywords

  • computational complexity theory
  • combinatorial computational geometry

Affiliated Academic Societies

  • The Institute of Electronics, Information and Communication Engineers, 1988
    Related URL
  • Information Processing Society of Japan, 1990
    Related URL

Educational Activity

Course in Charge

  1. 2025, Liberal Arts Education Program1, 3Term, Linear AlgebraII
  2. 2025, Liberal Arts Education Program1, 1Term, Introductory Seminar for First-Year Students
  3. 2025, Undergraduate Education, 2Term, Discrete Mathematics I
  4. 2025, Undergraduate Education, 1Term, Theory of Automata and Languages
  5. 2025, Undergraduate Education, 1Term, Frontier of Informatics and Data Science
  6. 2025, Undergraduate Education, Intensive, Research Project
  7. 2025, Undergraduate Education, Intensive, Long-term Fieldwork I
  8. 2025, Undergraduate Education, 1Term, Computer Science Seminar I
  9. 2025, Undergraduate Education, 2Term, Computer Science Seminar II
  10. 2025, Undergraduate Education, Second Semester, Graduation Thesis
  11. 2025, Graduate Education (Master's Program) , 1Term, Special Exercises on Informatics and Data Science A
  12. 2025, Graduate Education (Master's Program) , 2Term, Special Exercises on Informatics and Data Science A
  13. 2025, Graduate Education (Master's Program) , 3Term, Special Exercises on Informatics and Data Science B
  14. 2025, Graduate Education (Master's Program) , 4Term, Special Exercises on Informatics and Data Science B
  15. 2025, Graduate Education (Master's Program) , Year, Special Study on Informatics and Data Science
  16. 2025, Graduate Education (Master's Program) , 3Term, Computational Complexity Theory
  17. 2025, Graduate Education (Doctoral Program) , Year, Special Study on Informatics and Data Science

Research Activities

Academic Papers

  1. Some Properties of Homogeneous Pyramid Automata, IEICE Transactions on Information and Systems (Japanese Edition), J73-D-I(9), 778-780, 19900901
  2. RS-Vector Algorithms for Combinatorial Problems, IEICE Transactions on Information and Systems (Japanese Edition), J75-D-I(3), 143-151, 19920301
  3. Parallelizabilities of Vertex Set Partition Problems, Proceedings of the Joint Symposium on Parallel Processing, 92(1), 47-53, 19920601
  4. RS-Vector Algorithms for Combinational Problems, Systems and Computers in Japan, 24(7), 41-51, 19930701
  5. Extended Graph Connectivity and Its Gradually Increasing Parallel Complexity, Proceedings of the fifth Annual International Symposium on Algorithms and Computation (Lecture Notes in Computer Science), 834, 478-486, 19940801
  6. Finding Hamiltonian Circuits in Arrangements of Jordan Curves is NP-Complete, Proceedings of the Sixth Canadian Conference on Computational Geometry, 93-98, 19940801
  7. Finding Hamiltonian circuits in arrangements of Jordan Curves Is NP-complete, Information Processing Letters, 52, 183-189, 19941101
  8. On Problems with Gradually Increasing Parallel Complexities, Proceedings of the 1996 IEICE General Conference, 361-362, 19960301
  9. A Faster Parallel Algorithm for k-Connectivity, Proceedings of the Second Korea-Japan Joint Workshop on Algorithms and Computation, 8-13, 19960401
  10. Parallel Complexity Hierarchies Based on PRAMs and DLOGTIME-Uniform Circuits, Proceedings of the Eleventh Annual IEEE Conference on Computational Complexity, 24-32, 19960501
  11. Alpha-Connectivity: A Gradually Nonparallel Graph Problem, Journal of Algorithms, 20(3), 526-544, 19960501
  12. Time Lower Bounds Do Not Exist for CRCW PRAMs, Theoretical Computer Science, 155, 411-424, 19960601
  13. How Can We Demonstrate Increasing Parallel Complexities?, ACM/UMIACS Fourth Workshop on Parallel Algorithms, 19970501
  14. Time Complexity Hierarchies of Extended TMs for Parallel Computation, IEICE Transactions on Information and Systems (Japanese Edition), J80-D-I(5), 421-427, 19970501
  15. A Faster Parallel Algorithm for k-Connectivity, Information Processing Letters, 61, 265-269, 19970601
  16. (1+o(1))S(n)-Space Is Stronger Than S(n)-Space, Proceedings of the 3rd JAPAN-KOREA Joint Workshop on Algorithms and Computation, 72-79, 19970701
  17. A Canonical Form of Vector Machines, Information and Computation, 141(1), 37-65, 19980401
  18. Complexity Hierarchies on DLOGTIME-Uniform Circuits and TMs with Restricted Symbols, Proceedings of the Eleventh Workshop on Circuits and Systems in Karuizawa, 367-372, 19980401
  19. Improved Time and Space Hierarchies of One-Tape Off-Line TMs, Proceedings of the 23rd International Symposium on Mathematical Foundations of Computer Science (Lecture Notes of Computer Science), 1450, 580-588, 19980801
  20. Periodic Recession and R＆D Management in Japan, Proceedings of the IEEE EMS International Engineering Management Conference, 198-201, 19990501
  21. Space Hierarchies of Turing Machines with Restricted Tape Symbols, IEICE Transactions on Information and Systems (Japanese Edition), J82-D-I(6), 661-668, 19990601
  22. Technological Changes and the Effect of Business Cycles in Electric Manufacturing Companies for the Postwar 50 Years, Transactions of the Institute of Electrical Engineers of Japan (Japanese Edition), 119-A(6), 725-730, 19990601
  23. Juglar Cycles and Their Effects on Technological Changes, Portland International Conference on Management of Engineering and Technology, Proceedings Vol-1: Book of Summaries, Proceedings Vol-2: Papers Presented at PICMET’99, 1,2, 17-34, 19990701
  24. On Time-Constructible Functions in One-Dimensional Cellular Automata, Proceedings of the 12th International Symposium on Fundamentals of Computation Theory (Lecture Notes in Computer Science), 1684, 316-326, 19990801
  25. Universality of the Language Generating Ability of Two-Point Splicing Systems, IEICE Transactions on Information and Systems (Japanese Edition), J83-DI(1), 55-59, 20000101
  26. Application of Finite Difference Method to Arbitrary Mesh Points, Transactions of The Institute of Electrical Engineers of Japan (Japanese Edition), 120-A(2), 116-121, 20000201
  27. Speeding-Up Cellular Automata by Alternations, Proceedings of Machines Computations and Universality (Lecture Notes in Computer Science), 2055, 240-251, 20010501
  28. A three-dimensional uniquely parsable array grammar that generates and parses cubes, Electric Notes in Theoretical Comupter Science, 46, 1-16, 20010801
  29. Constructible functions in cellular automata and their applications to hierarchy results, Theoretical Computer Science, 270(1-2), 797-809, 20020106
  30. Computational Complexity in the Hyperbolic Plane, Proceedings of the 27th International Symposium on Mathematical Foundations of Computer Science (Lecture Notes in Computer Science), 2420, 365-374, 20020801
  31. Embedding a logically universal model and a self-reproducing model into number-conserving cellular automata, Proceedings of the Third International Conference on Unconventional Models of Computation (UMC2002) Lecture Notes in Computer Science), 2509, 164-175, 20021015
  32. A quadratic speedup theorem for iterative arrays, Acta Informatica, 38(11-12), 847-858, 20021101
  33. Self-reproduction and shape formation in two and three dimensional cellular automata with conservative constraints, Proceedings of the Eighth International Symposium on Artificial Life and Robotics (AROB2003), 377-380, 20030101
  34. Simulations between multi-dimensional deterministic and alternating cellular automata, Fundamenta Informaticae, 58(3-4), 261-271, 20031201
  35. A logically universal number-conserving cellular automaton with a unary table-lookup function, IEICE Transactions on Information and Systems, E87D(3), 694-699, 20040301
  36. Time and space complexity classes of hyperbolic cellular automata, IEICE Transactions on Information and Systems, E87D(3), 700-707, 20040301
  37. Prefix computations on iterative arrays with sequential input/output mode, IEICE Transactions on Information and Systems, E87D(3), 708-712, 20040301
  38. Partially effective randomization in simulations between ARBITRARY and COMMON PRAMs, Journal of Parallel and Distributed Computing, 64(3), 319-326, 20040301
  39. Hierarchies of DLOGTIME-Uniform Circuits, M. Margenstern (ed.): Machines Computations and Universality (Proc. MCU 2004 Saint-Petersburg Russia= September 21-26= 2004) Lecture Notes in Computer Science, 3354, 211-222, 20050201
  40. Translational lemmas for alternating TMs and PRAMs, FUNDAMENTALS OF COMPUTATIONAL THEORY, Proceedings of the 15th International Symposium on Fundamentals of Computation Theory (Lecture Notes in Computer Science), 3623, 137-148, 20050817
  41. A five-state von Neumann neighbor universal hyperbolic cellular automaton, Journal of Cellular Automata, 1(4), 275-297, 20061201
  42. A Time Hierarchy Theorem for Nondeterministic Cellular Automata, Proceedings of the 4th Annual Conference on Theory and Applications of Models of Computation (Lecture Notes in Computer Science), 4484, 511-520, 20070501
  43. Translational Lemmas for DLOGTIME-uniform Circuits, Alternating TMs, and PRAMs, Acta Informatica, 44(5), 345-359, 20070501
  44. Special Section on Foundations of Computer Science, IEICE Transactions on Information and Systems, E91-D(2), 161-161, 20080201
  45. A Java Based Three-Dimensional Cellular Automata Simulator and its Application to Three-Dimensional Larger Than Life, Proceedings of Automata 2008: Theory and Applications of Cellular Automata, Bristol, UK, Luniver Press, 413-416, 20080601
  46. A recursive padding technique on nondeterministic cellular automata, IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences, E91A(9), 2335-2340, 20080901
  47. On the non-existence of rotation-symmetric von Neumann neighbor number-conserving cellular automata of which the state number is less than four, IEICE Transactions on Information and Systems, E92-D(2), 255-257, 20090201
  48. An Efficient Reconstruction Algorithm for Restricted Domino Tilings, IEICE Transactions on Information and Systems (Japanese Edition), J92-D(6), 758-766, 20090601
  49. Computational Complexity of Cast Puzzles, Proceedings of the 20th International Symposium on Algorithms and Computation (Lecture Notes in Computer Science), 5878, 122-131, 20091201
  50. On designing gliders in three-dimensional Larger Than Life cellular automata, F. Peper et al. (eds.): Natural Computing (Proceedings in Information and Communications Technology), 2, 184-190, 20100201
  51. A Tight Space-Hierarchy Theorem for Nondeterministic Turing Machines, IEICE Transactions on Information and Systems (Japanese Edition), J93-D(9), 1717-1726, 20100901
  52. NP-Hard and k-EXPSPACE-Hard Cast Puzzles, IEICE Transactions on Information and Systems, E93D(11), 2995-3004, 20101101
    Link to Paper Search Results by DOI
  53. Relationship between Depth and Nondeterministic Gates in Nondeterministic Circuit Families, IPSJ Journal (Japanese Edition), 5(4), 1667-1677, 20110401
  54. Computational Complexity of String Puzzles, Proceedings of the 18th Computing: the Australasian Theory Symposium (CRPIT, 128, Mestre, J. Eds., ACS.), 128, 69-74, 20120101
  55. Lower Bound of Face Guards of Polyhedral Terrains, Journal of Information Processing, 20(2), 435-437, 20120401
  56. A Polynomial-Time Reduction from the 3SAT Problem to the Generalized String Puzzle Problem", Algorithms, 5(2), 261-272, 20120401
  57. Improved Lower and Upper Bounds of Face Guards of Polyhedral Terrains, Transactions on Information and Systems (Japanese Edition), J95-D(10), 1869-1872, 20121001
  58. Generalized Shisen-Sho is NP-Complete, IEICE Transactions on Information and Systems, E95D(11), 2712-2715, 20121101
    Link to Paper Search Results by DOI
  59. Finding the Minimum Number of Face Guards is NP-Hard, IEICE Transactions on Information and Systems, E95D(11), 2716-2719, 20121101
    Link to Paper Search Results by DOI
  60. Generalized Chat Noir is PSPACE-Complete, IEICE Transactions on Information and Systems, E96D(3), 502-505, 20130301
    Link to Paper Search Results by DOI
  61. Locating the Minimum Number of Guards with r-visibility in a Polyomino is NP-hard, The 16th Japan Conference on Discrete and Computational Geometry and Graphs (JCDCGG 2013), 100-101, 20130901
  62. Generalized Pyramid is NP-Complete, IEICE Transactions on Information and Systems, E96D(11), 2462-2465, 20131101
    Link to Paper Search Results by DOI
  63. Universal von Neumann Neighborhood Cellular Automata on Penrose Tilings, Proceedings of the 1st International Workshop on Applications and Fundamentals of Cellular Automata, 515-521, 20131201
  64. Yosenabe is NP-complete, Journal of Information Processing, 22(1), 40-43, 20140101
  65. Computational Complexity of the r-visibility Guard Set Problem for Polyominoes, Lecture Notes in Computer Science, Springer-Verlag, 8845, 87-95, 20141101
  66. Computational Complexity of Generalized Forty Thieves, IEICE Transactions on Information and Systems, E98D(2), 429-432, 20150201
    Link to Paper Search Results by DOI
  67. Computational Complexity of Generalized Golf Solitaire, IEICE Transactions on Information and Systems, E98D(3), 541-544, 20150301
    Link to Paper Search Results by DOI
  68. Visibility Problems for Manhattan Towers, IEICE Transactions on Information and Systems, E99-D(3), 607-614, 20160301
  69. Computational Complexity of Building Puzzles, IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences, E99-A(6), 1145-1148, 20160601
  70. Finding the Minimum Number of Open-Edge Guards in an Orthogonal Polygon is NP-hard, IEICE Transactions on Information and Systems, E100-D(7), 1521-1525, 20170701
  71. NP-completeness of Mojipittan, IEICE Transactions on Information and Systems (Japanese Edition), J100-D(12), 974-977, 20171201
  72. Dosun-Fuwari is NP-complete, Journal of Information Processing, 26, 358-361, 20180401
  73. Herugolf and Makaro are NP-complete, Proceedings of the Ninth International Conference on Fun with Algorithms (FUN 2018), 100(24), 24:1-24:11, 20180613
  74. Computational Complexity of Usowan Puzzles, IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences, E101-A(9), 1537-1540, 20180901
  75. Kurotto and Juosan are NP-complete, The 21st Japan Conference on Discrete and Computational Geometry, Graphs, and Games (JCDCG^3 2018), 46-48, 20180901
  76. Nurimisaki and Sashigane are NP-complete, The 31st Canadian Conference on Computational Geometry (CCCG 2019), 184-194, 20190801
  77. Computational Complexity of Herugolf and Makaro, IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences, E102-A(9), 1118-1125, 20190901
  78. Polynomial-Time Reductions from 3SAT to Kurotto and Juosan Puzzles, IEICE Transactions on Information and Systems, E103-D(3), 500-505, 20200301
    Link to Paper Search Results by DOI
  79. Computational Complexity of the Chromatic Art Gallery Problem for Orthogonal Polygons, The 14th International Conference and Workshop on Algorithms and Computation (R.M. Sohel et al.(Eds): WALCOM 2020, Lecture Notes in Computer Science), 12049, 146-157, 20200401
    Link to Paper Search Results by DOI
  80. Computational Complexity of Nurimisaki and Sashigane, IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences, E103-A(10), 1183-1192, 20201001
    Link to Paper Search Results by DOI
  81. Chromatic Art Gallery Problem with r-visibility is NP-complete, IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences, E104-A(9), 1108-1115, 20210901
  82. Computational Complexity of Two Pencil Puzzles: Kurotto and Juosan, Lecture Notes in Computer Science, Springer-Verlag, 13034, 175-185, 20211101
  83. Five Cells and Tilepaint are NP-complete, IEICE Transactions on Information and Systems, E105-D(3), 508-516, 20220301
  84. Vertex-to-Point Conflict-Free Chromatic Guarding is NP-hard, Lecture Notes in Computer Science, Springer-Verlag, 13174, 111-122, 20220324
  85. Moon-or-Sun, Nagareru, and Nurimeizu are NP-complete, IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences, E105-A(9), 1187-1194, 20220901
  86. Calculation Solitaire is NP-complete, IEICE Transactions on Information and Systems, E106-D(3), 328-332, 20230301
  87. Computational Complexity of Sukoro, IEICE Transactions on Information and Systems, J106-D(5), 357-361, 20230501
  88. Yajisan-Kazusan and Stained Glass are NP-complete, The 23rd Japan-Korea Joint Workshop on Algorithms and Computation, 227-233, 20230624
  89. Computational Complexity of the Vertex-to-Point Conflict-Free Chromatic Art Gallery Problem, IEICE Transactions on Information and Systems, E106-D(9), 1499-1506, 20230901
  90. Chained Block is NP-complete, IEICE Transactions on Information and Systems, E107-D(3), 320-324, 20240301
  91. Choco Banana is NP-complete, IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences, E107-A(9), 1488-1491, 20240901
  92. The Chromatic Dispersive Art Gallery Problem, The 26th Japan Conference on Discrete and Computational Geometry, Graphs, and Games (JCDCG3), 120-121, 20240910
  93. Computational Complexity of Yajisan-Kazusan and Stained Glass, IEICE Transactions on Information and Systems, E108-D(3), 201-207, 20250301
  94. Shinkamino is NP-complete, IEICE Transactions on Information and Systems (Japanese Edition), J108-D(4), 199-203, 20250401
  95. Card-Based Zero-Knowledge Proof for Dosun-Fuwari, IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences, E108-A(9), 1-5, 20250901

Publications such as books

  1. 2003/11, Quantum Computing, 2003, 11, Scholarly Book, Joint Translation, 9784627827912, 491
  2. 2010/02, Hierarchy Theorems, 2010, 02, Dictionary/Encyclopedia, Cocompilation, 3

Invited Lecture, Oral Presentation, Poster Presentation

  1. How Can We Demonstrate Increasing Parallel Complexities?, Chuzo Iwamoto, ACM/UMIACS Fourth Workshop on Parallel Algorithms (WOPA1996), 1996/05, With Invitation, English, ACM/UMIACS, Philadelphia, USA
  2. Complexity Hierarchies on DLOGTIME-Uniform Circuits and TMs with Restricted Symbols, Chuzo Iwamoto, Eleventh Workshop on Circuits and Systems in Karuizawa, 1998/04, With Invitation, Japanese, Nagano
  3. Complexity Hierarchies on Turing Machines, Uniform Circuits, and Cellular Automata, Chuzo Iwamoto, Abstracts of Invited Lectures and Short Communications Delivered at the Ninth CNACSA, 2000/08, With Invitation, English, Bulgaria

Awards

  1. 1993/03, Telecom-Columbus Award, Telecommunications Advancement Foundation, RS-Vector Algorithms for Combinatorial Problems
  2. 2008/01, 2007 LA/EATCS Best Presentation Award, LA Symposium, EATCS Japan Chapter, Reconstruction of Unicolored Domino Tilings of Degree Five from Orthogonal Projections
  3. 2009/11/26, The ISS Distinguished Service Award, President of IEICE Information and Systems Society, Contribution as an editor of IEICE Transactions on Information and Systems
  4. 2011/06, The ISS Distinguished Reviewer Award, President of IEICE Information and Systems Society, Contribution as a reviewer of IEICE Transactions
  5. 2018/02/06, 2017 LA/EATCS Best Presentation Award, LA Symposium, EATCS Japan Chapter, Herugolf is NP-complete