Kengo Nakamura

Associate Distinguished Researcher of
Linguistic Intelligence Research Group
Innovative Communication Laboratory
NTT Communication Science Laboratories

Doctor of Informatics


Contact Information:
kengo.nakamura (at) ntt.com
2-4 Hikaridai, Seika, Souraku,
Kyoto 619-0237, JAPAN

C.V.

Education

Employment

Research Interests

  • Algorithms and computation
  • Data structures
  • Discrete structure manipulation system
  • Binary decision diagram (BDD) and variants
  • Succinct data structures
  • Dynamic graph algorithms
  • Network reliability

Publication

  • Refereed Paper
  • Misc

Journal Paper

  1. Takeru Inoue, Akira Ito, Kengo Nakamura, Tatsuya Matsukawa:
    Impact of facility factors on robustness of communication networks under natural disasters.
    IEEE Communications Magazine, 2024, accepted.
  2. Kengo Nakamura, Kunihiko Sadakane:
    Space-Efficient fully dynamic DFS in undirected graphs.
    Algorithms, Vol. 12(3), No. 52, 2019. [paper]

Conference Paper

  1. Kengo Nakamura, Masaaki Nishino, Shuhei Denzumi:
    Single family algebra operation on BDDs and ZDDs leads to exponential blow-up.
    The 35th International Symposium on Algorithms and Computation (ISAAC2024), to appear.
  2. Kengo Nakamura, Takeru Inoue, Masaaki Nishino, Norihito Yasuda:
    Outage-scale-based network reliability evaluation for severe reliability requirements.
    The 2024 IEEE Global Communications Conference (GLOBECOM2024), to appear.
  3. Kengo Nakamura, Takeru Inoue, Masaaki Nishino, Norihito Yasuda:
    Efficient and exact algorithm for all pair-wise network reliability and its applications to enhance unreliable pairs.
    The 2024 IEEE Global Communications Conference (GLOBECOM2024), to appear.
  4. Masaaki Nishino, Kengo Nakamura, Norihito Yasuda:
    Understanding the impact of introducing constraints at inference time on generalization error.
    The 41st International Conference on Machine Learning (ICML2024), PMLR Vol. 235, pp. 38253--38263, 2024. [paper (mlr.press)]
  5. Kengo Nakamura, Masaaki Nishino, Norihito Yasuda, Shin-ichi Minato:
    CompDP: a framework for simultaneous subgraph counting under connectivity constraints.
    The 21st Symposium on Experimental Algorithms (SEA2023), LIPIcs Vol. 265, pp 11:1--11:20, 2023. [paper] [implementation]
  6. Kengo Nakamura, Takeru Inoue, Masaaki Nishino, Norihito Yasuda, Shin-ichi Minato:
    Exact and efficient network reliability evaluation per outage scale.
    The 2023 IEEE International Conference on Communications (ICC2023), pp. 4564--4570, 2023. [paper] [implementation]
  7. Kengo Nakamura, Takeru Inoue, Masaaki Nishino, Norihito Yasuda, Shin-ichi Minato:
    A fast and exact evaluation algorithm for the expected number of connected nodes: an enhanced network reliability measure.
    The 2023 IEEE International Conference on Computer Communications (INFOCOM2023), pp. 1--10, 2023. [paper] [implementation]
  8. Masaaki Nishino, Kengo Nakamura, Norihito Yasuda:
    Generalization analysis on learning with a concurrent verifier.
    The 36th Conference on Neural Information Processing Systems (NeurIPS2022), 2022. [paper (NeurIPS proceedings)] [full version (arXiv)]
  9. Ryoma Onaka, Kengo Nakamura, Takeru Inoue, Masaaki Nishino, Norihito Yasuda, Shinsaku Sakaue:
    Exact and scalable network reliability evaluation for probabilistic correlated failures.
    The 2022 IEEE Global Communications Conference (GLOBECOM2022), pp 5547--5552, 2022. [paper]
  10. Kengo Nakamura, Takeru Inoue, Masaaki Nishino, Norihito Yasuda:
    Impact of link availability uncertainty on network reliability: analyses with variances.
    The 2022 IEEE International Conference on Communications (ICC2022), pp 2713--2719, 2022. [paper] [implementation]
  11. Shinsaku Sakaue, Kengo Nakamura:
    Differentiable equilibrium computation with decision diagrams for Stackelberg models of combinatorial congestion games.
    The 35th Conference on Neural Information Processing Systems (NeurIPS2021), pp. 9416--9428, 2021. [paper (NeurIPS proceedings)] [full version (arXiv)] [implementation]
  12. Kengo Nakamura, Takeru Inoue, Masaaki Nishino, Norihito Yasuda:
    Efficient network reliability evaluation for client-server model.
    The 2021 IEEE Global Communications Conference (GLOBECOM2021), pp. 1--6, 2021. [paper] [implementation]
  13. Masaaki Nishino, Norihito Yasuda, Kengo Nakamura:
    Compressing exact cover problems with zero-suppressed binary decision diagrams.
    The 30th International Joint Conference on Artificial Intelligence (IJCAI2021), pp. 1996--2004, 2021. [paper]
  14. Kengo Nakamura, Shuhei Denzumi, Masaaki Nishino:
    Variable Shift SDD: a more succinct and canonical sentential decision diagram.
    The 18th Symposium on Experimental Algorithms (SEA2020), LIPIcs Vol. 160, pp. 22:1--22:13, 2020. [paper] [full version (arXiv)]
  15. Kengo Nakamura, Shinsaku Sakaue, Norihito Yasuda:
    Practical Frank--Wolfe method with decision diagrams for computing Wardrop equilibrium of combinatorial congestion games.
    The 34th AAAI Conference on Artificial Intelligence (AAAI2020), pp. 2200--2209, 2020. [paper]
  16. Naoki Kobayashi, Tsutomu Hirao, Kengo Nakamura, Hidetaka Kamigaito, Manabu Okumura, Masaaki Nagata:
    Split or merge: Which is better for unsupervised RST parsing?
    2019 Conference on Empirical Methods in Natural Language Processing (EMNLP2019), pp. 5797--5802, 2019. [paper]
  17. Kotaro Matsuda, Shuhei Denzumi, Kengo Nakamura, Masaaki Nishino, Norihito Yasuda:
    Approximated ZDD construction considering inclusion relations of models.
    Special Event on Analysis of Experimental Algorithms (SEA^2 2019), LNCS Vol. 11544, pp. 265--282, 2019. [paper]
  18. Kengo Nakamura:
    Fully dynamic connectivity oracles under general vertex updates.
    The 28th International Symposium on Algorithms and Computation (ISAAC2017), LIPIcs Vol. 92, pp. 59:1--59:12, 2017. [paper]
  19. Kengo Nakamura, Kunihiko Sadakane:
    A space-efficient algorithm for the dynamic DFS problem in undirected graphs.
    The 11th International Conference and Workshops on Algorithms and Computation (WALCOM2017), LNCS Vol. 10167, pp. 295--307, 2017. [paper]

Misc

  1. 中村 健吾：
    圧縮計算でめざす高信頼インフラ ――決定グラフを用いたネットワーク解析問題の高速な解法．
    NTT技術ジャーナル, Vol.36, No.9, pp. 14--17, 2024. [article (in Japanese)]
  2. Kengo Nakamura, Masaaki Nishino, Shuhei Denzumi:
    Single family algebra operation on ZDDs leads to exponential blow-up.
    arXiv [paper (arXiv)]
  3. 中村 健吾：
    主役登場：アルゴリズムの力で高信頼なネットワークをめざす．
    NTT技術ジャーナル, Vol.35, No.8, p. 27, 2023. [article (in Japanese)]
  4. Masaaki Nishino, Kengo Nakamura, Norihito Yasuda:
    Generalization analysis on learning with a concurrent verifier.
    arXiv, Full version of the paper of NeurIPS2022 [paper (arXiv)]
  5. Shinsaku Sakaue, Kengo Nakamura:
    Differentiable equilibrium computation with decision diagrams for Stackelberg models of combinatorial congestion games.
    arXiv, Full version of the paper of NeurIPS2021 [paper (arXiv)]
  6. Kengo Nakamura, Shuhei Denzumi, Masaaki Nishino:
    Variable Shift SDD: a more succinct and canonical sentential decision diagram.
    arXiv, Full version of the paper of SEA2020 [paper (arXiv)]
  7. 中村 健吾，伝住 周平，西野 正彬：
    変数シフトの導入による項分岐決定図の省空間化．
    第11回データ工学と情報マネジメントに関するフォーラム (DEIM2019) 発表論文集, I1-4, 2019.
  8. 小林 尚輝，平尾 努，中村 健吾，上垣外 英剛，奥村 学，永田 昌明：
    テキストセグメンテーションによる教師なし修辞構造解析．
    言語処理学会第25回年次大会 (NLP2019) 発表論文集, D5-3, 2019.
  9. 中村 健吾，定兼 邦彦：
    無向グラフ動的DFSに対する省空間かつ高速なアルゴリズム．
    電子情報通信学会総合大会講演論文集，情報・システム講演論文集, pp. S-1--S-2, 2017.
  10. 中村 健吾，定兼 邦彦：
    無向グラフDFS木の動的更新アルゴリズムの省スペース化．
    2016年度夏のLAシンポジウム, pp. 24-1--24-7, 2016.

Talk

  • International Talks
  • Domestic Talks

International Talks

  1. Kengo Nakamura, Masaaki Nishino, Norihito Yasuda, Shin-ichi Minato:
    CompDP: a framework for simultaneous subgraph counting under connectivity constraints.
    The 21st Symposium on Experimental Algorithms (SEA2023), Barcelona, Spain, July 2023.
  2. Kengo Nakamura, Takeru Inoue, Masaaki Nishino, Norihito Yasuda, Shin-ichi Minato:
    Exact and efficient network reliability evaluation per outage scale.
    The 2023 IEEE International Conference on Communications (ICC2023), Rome, Italy, May 2023.
  3. Kengo Nakamura, Takeru Inoue, Masaaki Nishino, Norihito Yasuda, Shin-ichi Minato:
    A fast and exact evaluation algorithm for the expected number of connected nodes: an enhanced network reliability measure.
    The 2023 IEEE International Conference on Computer Communications (INFOCOM2023), Hoboken, NJ, USA, May 2023.
  4. Kengo Nakamura, Takeru Inoue, Masaaki Nishino, Norihito Yasuda:
    Impact of link availability uncertainty on network reliability: analyses with variances.
    The 2022 IEEE International Conference on Communications (ICC2022), Held in hybrid manner (Seoul, Korea), May 2022.
  5. Shinsaku Sakaue, Kengo Nakamura:
    Differentiable equilibrium computation with decision diagrams for Stackelberg models of combinatorial congestion games.
    The 35th Conference on Neural Information Processing Systems (NeurIPS2021), Held online, December 2021.
  6. Kengo Nakamura, Takeru Inoue, Masaaki Nishino, Norihito Yasuda:
    Efficient network reliability evaluation for client-server model.
    The 2021 IEEE Global Communications Conference (GLOBECOM2021), Held in hybrid manner (Madrid, Spain), December 2021.
  7. Kengo Nakamura, Shuhei Denzumi, Masaaki Nishino:
    Variable Shift SDD: a more succinct and canonical sentential decision diagram.
    The 18th Symposium on Experimental Algorithms (SEA2020), Held online (Catania, Italy), June 2020.
  8. Kengo Nakamura, Shinsaku Sakaue, Norihito Yasuda:
    Practical Frank--Wolfe method with decision diagrams for computing Wardrop equilibrium of combinatorial congestion games. (poster)
    The 34th AAAI Conference on Artificial Intelligence (AAAI2020), New York, USA, February 2020.
  9. Kengo Nakamura:
    Fully dynamic connectivity oracles under general vertex updates.
    The 28th International Symposium on Algorithms and Computation (ISAAC2017), Phuket, Thailand, December 2017.
  10. Kengo Nakamura, Kunihiko Sadakane:
    A space-efficient algorithm for the dynamic DFS problem in undirected graphs.
    TThe 11th International Conference and Workshops on Algorithms and Computation (WALCOM2017), Hsinchu, Taiwan, March 2017.

Domestic Talks

  1. 中村 健吾：
    ネットワーク信頼性解析とフロンティア法．
    離散数学とその応用研究部会2024 組合せ最適化ミニシンポジウム, Yamagata, August 2024.
  2. 中村 健吾：
    圧縮計算でめざす高信頼インフラ ー決定グラフを用いたネットワーク解析問題の高速な解法ー．
    NTTコミュニケーション科学基礎研究所 オープンハウス2024, Osaka, June 2024. [Research Talk]
  3. 中村 健吾：
    ZDD上でFamily Algebraの各種演算は指数時間かかる．
    学術変革(A)「社会変革アルゴリズム基盤」2024年度第1回領域集会, Sapporo, June 2024.
  4. 中村 健吾，井上 武，西野 正彬，安田 宜仁，湊 真一：
    Exact and Efficient Network Reliability Evaluation per Outage Scale．(poster)
    CREST「信頼されるAIシステム」2024年度上期ワークショップ, Tokyo, May 2024.
  5. 中村 健吾：
    ネットワーク信頼性各種尺度計算．
    学術変革(A)「社会変革アルゴリズム基盤」2023年度第2回領域集会, Atami (Shizuoka), October 2023.
  6. 中村 健吾，西野 正彬，安田 宜仁，湊 真一：
    CompDP: 複数の連結性制約の下の部分グラフ数え上げを同時に行う動的計画法．
    2023年度人工知能学会全国大会 OS-9 AIと制約プログラミング, Kumamoto, June 2023.
  7. 中村 健吾：
    ネットワーク信頼性の分散値計算．
    学術変革(A)「社会変革アルゴリズム基盤」2022年度第1回領域集会, Tokyo, March 2022.
  8. 中村 健吾：
    ZDDを用いた微分可能計算による混雑ゲーム均衡最適化．(poster)
    情報処理学会第84回全国大会 イベント企画「革新的アルゴリズム基盤の構築に向けて」, Held in hybrid manner (Matsuyama), March 2022.
  9. 中村 健吾：
    ZDDを用いた微分可能計算による混雑ゲーム均衡最適化．
    学術変革(A)「社会変革アルゴリズム基盤」2021年度第2回領域集会, Held online, October 2021.
  10. 中村 健吾，藤井 浩一，石橋 保身，神谷 俊介，梅谷 俊治：
    集合分割問題に対する重みつき局所探索法の改良．
    RIMS研究集会「数理最適化の理論・アルゴリズム・応用」, Held online, August 2020.
  11. 中村 健吾，坂上 晋作，安田 宣仁：
    ZDDを用いた組合せ混雑ゲームの均衡計算．(poster)
    情報系 WINTER FESTA Episode 5 (理研AIP), Tokyo, December 2019.
  12. 中村 健吾，伝住 周平，西野 正彬：
    変数シフトの導入による項分岐決定図の省空間化．
    第11回データ工学と情報マネジメントに関するフォーラム (DEIM2019), Sasebo (Nagasaki), March 2019.
  13. 中村 健吾：
    頂点更新に対応した完全動的グラフ連結性オラクル．(poster)
    基盤(S)離散構造処理系プロジェクト 2017年度秋のワークショップ, Akkeshi (Hokkaido), November 2017.
  14. 中村 健吾，定兼 邦彦：
    無向グラフ動的DFSに対する省空間かつ高速なアルゴリズム．
    COMP-ELC学生シンポジウム，電子情報通信学会総合大会, Nagoya, March 2017.
  15. 中村 健吾，定兼 邦彦：
    無向グラフDFS木の動的更新アルゴリズムの省空間化．(poster)
    情報系 WINTER FESTA Episode 2 (JST河原林ERATO), Tokyo, December 2016.
  16. 中村 健吾：
    無向グラフ動的DFSの省空間実装について．
    基盤(S)離散構造処理系プロジェクト 2016年度秋のワークショップ, Sapporo, November 2016.
  17. 中村 健吾，定兼 邦彦：
    無向グラフDFS木の動的更新アルゴリズムの省スペース化．
    2016年度夏のLAシンポジウム, Heguri (Nara), July 2016.
  18. 中村 健吾，松尾 宇泰：
    重調和作用素の陽的なQTT分解とその応用．
    「行列・固有値問題の解法とその応用」研究部会，日本応用数理学会 第12回研究部会連合発表会, Kobe, March 2016.

Awards

  1. 人工知能学会 全国大会（第37回）優秀賞 (w/ Masaaki Nishino, Shin-ichi Minato)．
    The Japanese Society for Artificial Intelligence, July 2023.
  2. NTTコミュニケーション科学基礎研究所 所長表彰（研究開発賞） (w/ Takeru Inoue, Masaaki Nishino, Norihito Yasuda)．
    NTT Communication Science Laboratories, April 2023.
  3. NTTコミュニケーション科学基礎研究所 所長表彰（奨励賞）．
    NTT Communication Science Laboratories, April 2020.
  4. 東京大学 情報理工学系研究科長賞．
    The University of Tokyo, March 2018.
  5. ISAAC2017 Best Student Paper Award.
    The 28th International Symposium on Algorithms and Computation (ISAAC2017), December 2017.
  6. 東京大学 工学部長賞．
    The University of Tokyo, March 2016.