Intelligence through computational origami, puzzles, games

UEHARA Laboratory
Professor：UEHARA Ryuhei

E-mail：
［Research areas］
Theoretical Computer Science, Computational Complexity, Algorithm, Computational Geometry
［Keywords］
Computational Origami, Combinatorial Optimization, Graph Algorithms, Computational Complexity of Games and Puzzles

Skills and background we are looking for in prospective students

Regarding mathematics, basic discrete mathematics and graph theory are required. The subjects in the course "algorithm and data structure" will also be necessary. Students should have some interest in puzzles, puzzle-like things, origami, and algorithms.

What you can expect to learn in this laboratory

Research consists of three stages: grasping the problem to be studied first, solving the problem, and publishing the result. In master's research, it is not easy to find your own problem from scratch. Therefore, through learning basic fields such as graph algorithms, we aim to find unsolved problems and themes to solve. In this case, you acquire the ability to read journal papers in English. As for problem solving, we aim to gain the ability to master basic theory exactly. In research activities, it is also important to acquire sufficient presentation skills. Through a series of research activities, intellectual and fundamental skills to be a researcher will be acquired and long-term ability to solve problems will be improved.

【Job category of graduates】 Information communication / information processing industry, technical consultancy company, etc.

Research outline

Fig 1:A common development of two boxes.

Theoretical computer science is hidden within themes that seem not to be related to information science, such as origami and puzzles. For example, if "folding" is regarded as a basic operation, the act of "folding origami" corresponds to an algorithm in a computer. In other words, even with the same origami design, you can think of efficient procedures, or mathematically show the difficulty of certain problems. Such “abstraction of problems” actually has applications in all fields. That is, “devising the solution method theoretically” of the abstract problem is exactly the real pleasure of theoretical computer science.

Sometimes, it is theoretically shown that a certain problem is “hard and intractable”, and you are unwilling to give up. One of the main themes of the Uehara Laboratory is to give solutions with some relevance to such “difficult problems to compute” in a realistic time.

On the other hand, effective solutions may be found for certain problems. There should be a solution that no one knew until then, and the description of that solution is the “algorithm”. A good algorithm has a theoretical guarantee beyond just a thought. Theoretical guarantee of such an efficient algorithm is also one of the main themes of Uehara Lab.

Key publications

1. Takehiro Ito, Jun Kawahara, Shin-ichi Minato, Yota Otachi, Akira Suzuki, Ryuhei Uehara, Takeaki Uno, Katsuhisa Yamanaka, Ryo Yoshinaka, and Toshiki Saitoh. Sorting Balls and Water: Equivalence and Computational Complexity, Theoretical Computer Science, Vol. 978, 114158(15 pages), August, 2023. DOI:10.1016/j.tcs.2023.114158
2. Ryuhei Uehara. Computational Complexity of Puzzles and Related Topics, Interdisciplinary Information Sciences, Vol. 29, No. 2, pp. 119-140, December, 2023. DOI:10.4036/iis.2022.R.06
3. Erik D. Demaine, Martin L. Demaine, and Ryuhei Uehara. Developing a tetramonohedron with minimum cut length, Computational Geometry: Theory and Applications, Vol. 108, 101903(11 pages), 2022. DOI:10.1016/ j.comgeo.2022.101903