Chuzo Iwamoto

Last Updated :2021/04/15

Affiliations, Positions
Graduate School of Advanced Science and Engineering, Professor
Web Site
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

  • 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
  • 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
  • 2007/04/01, 2015/08/31, Hiroshima University, Graduate School of Engineering, Associate Professor
  • 2014/09/01, 2020/03/31, Hiroshima University, Graduate School of 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
  • 【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

  • hierarchy theorem
  • computational complexity
  • algorithm

Affiliated Academic Societies

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

Educational Activity

Course in Charge

  1. 2021, Liberal Arts Education Program1, 1Term, Elements of Calculus
  2. 2021, Liberal Arts Education Program1, 3Term, Linear AlgebraII
  3. 2021, Undergraduate Education, 1Term, Theory of Automata and Languages
  4. 2021, Graduate Education (Master's Program) , 1Term, Special Exercises on Informatics and Data Science A
  5. 2021, Graduate Education (Master's Program) , 2Term, Special Exercises on Informatics and Data Science A
  6. 2021, Graduate Education (Master's Program) , 3Term, Special Exercises on Informatics and Data Science B
  7. 2021, Graduate Education (Master's Program) , 4Term, Special Exercises on Informatics and Data Science B
  8. 2021, Graduate Education (Master's Program) , Academic Year, Special Study on Informatics and Data Science
  9. 2021, Graduate Education (Master's Program) , 3Term, Computational Complexity Theory
  10. 2021, Graduate Education (Doctoral Program) , Academic 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. Finding Hamiltonian Circuits in Arrangements of Jordan Curves is NP-Complete, Proceedings of the Sixth Canadian Conference on Computational Geometry, 93-98, 19940801
  6. 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
  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. Alpha-Connectivity: A Gradually Nonparallel Graph Problem, Journal of Algorithms, 20(3), 526-544, 19960501
  11. Parallel Complexity Hierarchies Based on PRAMs and DLOGTIME-Uniform Circuits, Proceedings of the Eleventh Annual IEEE Conference on Computational Complexity, 24-32, 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. Complexity Hierarchies on Circuits under Restricted Uniformities, Proceedings of the 10th International Conference on Computing and Information (Lecture Notes in Computer Science), 2023, 20001101
  28. Speeding-Up Cellular Automata by Alternations, Proceedings of Machines Computations and Universality (Lecture Notes in Computer Science), 2055, 240-251, 20010501
  29. A three-dimensional uniquely parsable array grammar that generates and parses cubes, Electric Notes in Theoretical Comupter Science, 46, 1-16, 20010801
  30. Constructible functions in cellular automata and their applications to hierarchy results, Theoretical Computer Science, 270(1-2), 797-809, 20020106
  31. 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
  32. 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
  33. A quadratic speedup theorem for iterative arrays, Acta Informatica, 38(11-12), 847-858, 20021101
  34. 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
  35. Simulations between multi-dimensional deterministic and alternating cellular automata, Fundamenta Informaticae, 58(3-4), 261-271, 20031201
  36. A logically universal number-conserving cellular automaton with a unary table-lookup function, IEICE Transactions on Information and Systems, E87D(3), 694-699, 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. Time and space complexity classes of hyperbolic cellular automata, IEICE Transactions on Information and Systems, E87D(3), 700-707, 20040301
  40. 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
  41. 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
  42. A five-state von Neumann neighbor universal hyperbolic cellular automaton, Journal of Cellular Automata, 1(4), 275-297, 20061201
  43. 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
  44. Translational Lemmas for DLOGTIME-uniform Circuits, Alternating TMs, and PRAMs, Acta Informatica, 44(5), 345-359, 20070501
  45. Special Section on Foundations of Computer Science, IEICE Transactions on Information and Systems, E91-D(2), 161-161, 20080201
  46. 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
  47. A recursive padding technique on nondeterministic cellular automata, IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences, E91A(9), 2335-2340, 20080901
  48. 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
  49. An Efficient Reconstruction Algorithm for Restricted Domino Tilings, IEICE Transactions on Information and Systems (Japanese Edition), J92-D(6), 758-766, 20090601
  50. Computational Complexity of Cast Puzzles, Proceedings of the 20th International Symposium on Algorithms and Computation (Lecture Notes in Computer Science), 5878, 122-131, 20091201
  51. 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
  52. A Tight Space-Hierarchy Theorem for Nondeterministic Turing Machines, IEICE Transactions on Information and Systems (Japanese Edition), J93-D(9), 1717-1726, 20100901
  53. NP-Hard and k-EXPSPACE-Hard Cast Puzzles, IEICE Transactions on Information and Systems, E93D(11), 2995-3004, 20101101
  54. Relationship between Depth and Nondeterministic Gates in Nondeterministic Circuit Families, IPSJ Journal (Japanese Edition), 5(4), 1667-1677, 20110401
  55. Computational Complexity of String Puzzles, Proceedings of the 18th Computing: the Australasian Theory Symposium (CRPIT, 128, Mestre, J. Eds., ACS.), 128, 69-74, 20120101
  56. Lower Bound of Face Guards of Polyhedral Terrains, Journal of Information Processing, 20(2), 435-437, 20120401
  57. A Polynomial-Time Reduction from the 3SAT Problem to the Generalized String Puzzle Problem", Algorithms, 5(2), 261-272, 20120401
  58. Improved Lower and Upper Bounds of Face Guards of Polyhedral Terrains, Transactions on Information and Systems (Japanese Edition), J95-D(10), 1869-1872, 20121001
  59. Generalized Shisen-Sho is NP-Complete, IEICE Transactions on Information and Systems, E95D(11), 2712-2715, 20121101
  60. Finding the Minimum Number of Face Guards is NP-Hard, IEICE Transactions on Information and Systems, E95D(11), 2716-2719, 20121101
  61. Generalized Chat Noir is PSPACE-Complete, IEICE Transactions on Information and Systems, E96D(3), 502-505, 20130301
  62. 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
  63. Generalized Pyramid is NP-Complete, IEICE Transactions on Information and Systems, E96D(11), 2462-2465, 20131101
  64. 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
  65. Yosenabe is NP-complete, Journal of Information Processing, 22(1), 40-43, 20140101
  66. Computational Complexity of the r-visibility Guard Set Problem for Polyominoes, Lecture Notes in Computer Science, Springer-Verlag, 8845, 87-95, 20141101
  67. Computational Complexity of Generalized Forty Thieves, IEICE Transactions on Information and Systems, E98D(2), 429-432, 20150201
  68. Computational Complexity of Generalized Golf Solitaire, IEICE Transactions on Information and Systems, E98D(3), 541-544, 20150301
  69. Visibility Problems for Manhattan Towers, IEICE Transactions on Information and Systems, E99-D(3), 607-614, 20160301
  70. Computational Complexity of Building Puzzles, IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences, E99-A(6), 1145-1148, 20160601
  71. 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
  72. NP-completeness of Mojipittan, IEICE Transactions on Information and Systems (Japanese Edition), J100-D(12), 974-977, 20171201
  73. Dosun-Fuwari is NP-complete, Journal of Information Processing, 26, 358-361, 20180401
  74. 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
  75. Computational Complexity of Usowan Puzzles, IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences, E101-A(9), 1537-1540, 20180901
  76. Kurotto and Juosan are NP-complete, The 21st Japan Conference on Discrete and Computational Geometry, Graphs, and Games (JCDCG^3 2018), 46-48, 20180901
  77. Nurimisaki and Sashigane are NP-complete, The 31st Canadian Conference on Computational Geometry (CCCG 2019), 184-194, 20190801
  78. Computational Complexity of Herugolf and Makaro, IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences, E102-A(9), 1118-1125, 20190901
  79. Polynomial-Time Reductions from 3SAT to Kurotto and Juosan Puzzles, IEICE Transactions on Information and Systems, E103-D(3), 500-505, 20200301
  80. 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
  81. Computational Complexity of Nurimisaki and Sashigane, IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences, E103-A(10), 1183-1192, 20201001
  82. Chromatic Art Gallery Problem with r-visibility is NP-complete, IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences, E104-A(9), 1-8, 20210901

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