Studies and Awards
Journal Articles
Tomu MAKITA Atsuki NAGAO Tatsuki OKADA Kazuhisa SETO Junichi TERUYAMA, "A Satisfiability Algorithm for Deterministic Width-2 Branching Programs." IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences, DOI: 10.1587/transfun.2021EAP1120
Kyohei Chiba, Rémy Belmonte, Hiro Ito, Michael Lampis, Atsuki Nagao, Yota Otachi. "K₃ Edge Cover Problem in a Wide Sense." Journal of Information Processing Vol.28 849–858, Dec., 2020.
Atsuki Nagao, Kazuhisa Seto, Junichi Teruyama. "Satisfiability Algorithm for Syntactic Read-k-times Branching Programs." Theory of Computing Systems, 64(8): 1392-1407 (2020)
Hiro Ito, Atsuki Nagao and Teagun Park. "Generalized Shogi, Chess, and Xiangqi are Constant-Time Testable." IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences, E102-A, 9, pp.1126-1133, Sep., 2019.
Kazuo Iwama and Atsuki Nagao, "Read-Once Branching Programs for Tree Evaluation Problems." ACM Transactions on Computation Theory, Volume 11 Issue 1, January 2019, Article No. 5
Atsuki Nagao, Kazuhisa Seto and Junich Teruyama, "A Moderately Exponential Time Algorithm for k-IBDD Satisfiability." Algorithmica, October 2018, Volume 80, Issue 10, pp 2725–2741.
Atsushi Hashimoto, Atsuki Nagao, and Satoru Okuda: Topological Graph Description of Multicellular Dynamics Based on Vertex Model. Journal of Theoretical Biology, 2018, 437: 187-201.
Etsuji Tomita, Sora Matsuzaki, Atsuki Nagao, Hiro Ito, and M. Wakatsuki: A Much Faster Algorithm for Finding a Maximum Clique with Computational Experiments. Journal of Information Processing, 2017, 25: 667-677.
Atsuki Nagao, Kazuhisa Seto, Junichi Teruyama. Efficient Algorithms for Sorting k-Sets in Bins, IEICE Transactions on Information and Systems, E98-D(10):1736-1743, October, 2015
Conferences
International
Atsuki Nagao and Sawako Ogawa. "Algorithms for Burning Schedule Reconfiguration Problem on Path Forests" The 24th Japan Conference on Discrete and Computational Geometry, Graphs, and Games (JCDCG^3 2022): September, 2022.
Shio Nagahara and Atsuki Nagao. "PSPACEcompleteness of generalized Quarto!" The 24th Japan Conference on Discrete and Computational Geometry, Graphs, and Games (JCDCG^3 2022): September, 2022.
Daiki Miyahara, Léo Robert, Pascal Lafourcade, So Takeshige, Takaaki Mizuki, Kazumasa Shinagawa, Atsuki Nagao, Hideaki Sone. "Card-Based ZKP Protocols for Takuzu and Juosan." 10th International Conference on Fun with Algorithms: 20:1-20:21
Pascal Lafourcade, Takaaki Mizuki, Atsuki Nagao, Kazumasa Shinagawa. "Light Cryptography." World Conference on Information Security Education 2019: 89-101
Xavier Bultel, Jannik Dreier, Jean-Guillaume Dumas, Pascal Lafourcade, Daiki Miyahara, Takaaki Mizuki, Atsuki Nagao, Tatsuya Sasaki, Kazumasa Shinagawa and Hideaki Sone: Physical Zero-Knowledge Proof for Makaro. 20th International Symposium on Stabilization, Safety, and Security of Distributed Systems (SSS 2018): November, 2018. Tokyo, Japan.
Atsuki Nagao and Maho Yokota: PSPACE-completeness for Snakebird. The 21th Japan Conference on Discrete and Computational Geometry, Graphs, and Games (JCDCG^3 2018): September, 2018.
Atsuki Nagao, Kazuhisa Seto and Junich Teruyama: Satisfiability Algorithm for Syntactic Read k-times Branching Programs. The 28th International Symposium on Algorithms and Computation, Proc. of ISAAC 2017, 58:1-58:10, December, 2017 (Phuket, Thailand).
Kyohei Chiba, Hiro Ito and Atsuki Nagao: K_3 edge cover in a wide sense. The 20th Japan Conference on Discrete and Computational Geometry, Graphs, and Games (JCDCG^3 2017): September, 2017.
Hiro Ito, Atsuki Nagao and Teagun Park: Constant-time testers for generalized shogi, chess, and xiangqi. The 19th Japan Conference on Discrete and Computational Geometry, Graphs, and Games (JCDCG^3 2016): September, 2016.
Etsuji Tomita, Kohei Yoshida, Takuro Hatta, Atsuki Nagao, Hiro Ito and Mitsuo Wakatsuki: A Much Faster Branch-and-Bound Algorithm for Finding a Maximum Clique. Frontiers in Algorithmics, 10th International Workshop (FAW 2016): 215-226, August 2016.
Hiro Ito, Atsuki Nagao and Teagun Park: Generalized shogi and chess are constant-time tastable. Proc. of the 12th International Symposium on Operations Research & Its Applications (ISORA): 41-44, August, 2015.
Atsuki Nagao, Kazuhisa Seto and Junichi Teruyama: A Moderately Exponential Time Algorithm fork-IBDD Satisfiability. Workshop on Algorithms and Data Structures (WADS) 2015: 554-565
Kazuo Iwama and Atsuki Nagao: Read-Once Branching Programs for Tree Evaluation Problems. Symposium on Theoretical Aspects of Computer Science (STACS) 2014: 409-420
Atsuki Nagao, Kazuhisa Seto and Junichi Teruyama: Efficient Algorithms for Sorting k-Sets in Bins. Workshop on Algorithms and Computation (WALCOM) 2014: 225-236
Invited Talk
Atsuki Nagao: Superpolynomial Lower Bound for Restricted Branching Programs Solving Tree Evaluation Problems. IEICE General Conference, DS-1-6, March 2017
Conference Organizing
The 10th International Conference on FUN with Algorithms (FUN2020)
The 9th International Conference on FUN with Algorithms (FUN2018)
The Japan Conference on Discrete and Computational Geometry, Graphs, and Games (JCDCG3) 2016,2017,2019,2022.
Awards
Young Researcher's Award, The Institute of Electronics, Information and Communication Engineers (IEICE), 2013
Best student paper award, IEICE Technical Committee on Theoretical Foundations of Computing (COMP), 2012