Intelligence through computational origami, puzzles, games
Theoretical Computer Science, Computational Complexity, Algorithm, Computational Geometry
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.
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.
- D. Xu, T. Horiyama, T. Shirakawa, and R. Uehara:Common Developments of Three Incongruent Boxes of Area 30, COMPUTATIONAL GEOMETRY: Theory and Applications, Vol. 64, pp. 1-17, August 2017.
- E. D. Demaine, D. Eppstein, A. Hesterberg, H. Ito, A. Lubiw, R. Uehara, and Y. Uno: Folding a Paper Strip to Minimize Thickness, Journal of Discrete Algorithms, Vol. 36, pp. 18-26, January, 2016.
- E. D Demaine, M. L Demaine, E. Fox-Epstein, D. A Hoang, T. Ito, H. Ono, Y. Otachi, R. Uehara, and T. Yamada: Linear-Time Algorithm for Sliding Tokens on Trees, Theoretical Computer Science, Vol. 600, pp. 132-142, October 2015.
This laboratory aims to understand the research of theoretical computer science and to train students who can perform it. Research in computer science have three points:
1) modeling abstract specific problems, 2) developing algorithms to solve problems, 3) theoretical evaluation of developed algorithms. It is the goal this laboratory to foster students with the power to perform these three. In addition, research results are always to be published in public. We believe that presentation of results is also important as a part of research. Students will hold seminars for learning purposes around once a week, using Japanese or English books and papers.