中村 健吾

日本電信電話株式会社
コミュニケーション科学基礎研究所
協創情報研究部
言語知能研究グループ
准特別研究員

博士（情報学）

連絡先:
kengo.nakamura (at) ntt.com
〒619-0237 京都府相楽郡精華町光台2-4

Research Interests

  • アルゴリズム・コンピュテーション
  • データ構造
  • 離散構造処理系
  • 二分決定グラフ(BDD)とその変種
  • 動的グラフアルゴリズム
  • 簡潔データ構造
  • ネットワーク信頼性

C.V.

Education

Employment

業績リスト

  • 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, Vol. 63, No. 1, pp. 138--144, 2025. [paper]
  2. Manami Ogawa, Ryoma Onaka, Kengo Nakamura, Shunsuke Kanai, Kenichi Tayama, Satoru Iwata:
    Bottleneck vehicle routing for planning power supply during disasters.
    Journal of the Operations Research Society of Japan, 2025, accepted.
  3. Kengo Nakamura, Kunihiko Sadakane:
    Space-Efficient fully dynamic DFS in undirected graphs.
    Algorithms, Vol. 12(3), No. 52, 2019. [paper]

Conference Paper

  1. Kaito Okamura, Kengo Nakamura, Takeru Inoue, Masaaki Nishino, Norihito Yasuda:
    Efficient network reliability evaluation with guaranteed error bound using binary decision diagrams.
    The 2025 IEEE International Conference on Communications (ICC2025), to appear.
  2. Ryoma Onaka, Kengo Nakamura, Masaaki Nishino, Norihito Yasuda:
    Tensor decomposition meets knowledge compilation: a study comparing tensor trains with OBDDs.
    The 39th Annual AAAI Conference on Artificial Intelligence (AAAI2025), pp. 15109--15117, 2025. [paper]
  3. Ryoma Onaka, Kengo Nakamura, Masaaki Nishino, Norihito Yasuda:
    An and-sum circuit with signed edges that is more succinct than SDD.
    The 39th Annual AAAI Conference on Artificial Intelligence (AAAI2025), pp. 15100--15108, 2025. [paper]
  4. 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), LIPIcs Vol. 322, pp. 52:1--52:17, 2024. [paper]
  5. 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), pp. 104--109, 2024. [paper] [implementation]
  6. 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), pp. 98--103, 2024. [paper] [implementation]
  7. 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)]
  8. 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]
  9. 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]
  10. 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]
  11. 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)]
  12. 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]
  13. 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]
  14. 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]
  15. 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]
  16. 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]
  17. 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)]
  18. 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]
  19. 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]
  20. 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]
  21. 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]
  22. 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. 中村 健吾:
    The Art of Computer Programmingの新たな誤りが発見される！ ─「二分決定グラフ」の演算にかかる最悪時間計算量を証明．
    情報処理学会学会誌「情報処理」, note, 2025. [記事]
  2. Ryoma Onaka, Kengo Nakamura, Masaaki Nishino, Norihito Yasuda:
    Tensor decomposition meets knowledge compilation: a study comparing tensor trains with OBDDs.
    arXiv, AAAI2025 採択論文のフルバージョン [paper (arXiv)]
  3. Kengo Nakamura:
    Towards Reliable Infrastructures with Compressed Computation．
    NTT Technical Review, Vol.22, No.11, pp. 23--28, 2024. [記事 (in English)]
  4. 中村 健吾：
    圧縮計算でめざす高信頼インフラ ――決定グラフを用いたネットワーク解析問題の高速な解法．
    NTT技術ジャーナル, Vol.36, No.9, pp. 14--17, 2024. [記事]
  5. Kengo Nakamura, Masaaki Nishino, Shuhei Denzumi:
    Single family algebra operation on BDDs and ZDDs leads to exponential blow-up.
    arXiv, ISAAC2024 採択論文のフルバージョン [paper (arXiv)]
  6. 中村 健吾：
    主役登場：アルゴリズムの力で高信頼なネットワークをめざす．
    NTT技術ジャーナル, Vol.35, No.8, p. 27, 2023. [記事]
  7. 中村 健吾，西野 正彬，安田 宜仁，湊 真一：
    CompDP: 複数の連結性制約の下の部分グラフ数え上げを同時に行う動的計画法．
    2023年度人工知能学会全国大会 (JSAI2023) 発表論文集, 2I5-OS-9b-03, 2023.
  8. Masaaki Nishino, Kengo Nakamura, Norihito Yasuda:
    Generalization analysis on learning with a concurrent verifier.
    arXiv, NeurIPS2022 採択論文のフルバージョン [paper (arXiv)]
  9. Shinsaku Sakaue, Kengo Nakamura:
    Differentiable equilibrium computation with decision diagrams for Stackelberg models of combinatorial congestion games.
    arXiv, NeurIPS2021 採択論文のフルバージョン [paper (arXiv)]
  10. Kengo Nakamura, Shuhei Denzumi, Masaaki Nishino:
    Variable Shift SDD: a more succinct and canonical sentential decision diagram.
    arXiv, SEA2020 採択論文のフルバージョン [paper (arXiv)]
  11. 中村 健吾，伝住 周平，西野 正彬：
    変数シフトの導入による項分岐決定図の省空間化．
    第11回データ工学と情報マネジメントに関するフォーラム (DEIM2019) 発表論文集, I1-4, 2019.
  12. 小林 尚輝，平尾 努，中村 健吾，上垣外 英剛，奥村 学，永田 昌明：
    テキストセグメンテーションによる教師なし修辞構造解析．
    言語処理学会第25回年次大会 (NLP2019) 発表論文集, D5-3, 2019.
  13. 中村 健吾，定兼 邦彦：
    無向グラフ動的DFSに対する省空間かつ高速なアルゴリズム．
    電子情報通信学会総合大会講演論文集，情報・システム講演論文集, pp. S-1--S-2, 2017.
  14. 中村 健吾，定兼 邦彦：
    無向グラフDFS木の動的更新アルゴリズムの省スペース化．
    2016年度夏のLAシンポジウム, pp. 24-1--24-7, 2016.

講演

  • International Talks
  • Domestic Talks

International Talks

  1. Ryoma Onaka, Kengo Nakamura, Masaaki Nishino, Norihito Yasuda:
    Tensor decomposition meets knowledge compilation: a study comparing tensor trains with OBDDs. (poster)
    The 39th Annual AAAI Conference on Artificial Intelligence (AAAI2025), フィラデルフィア，アメリカ，2025年2月．
  2. Ryoma Onaka, Kengo Nakamura, Masaaki Nishino, Norihito Yasuda:
    An and-sum circuit with signed edges that is more succinct than SDD. (oral & poster)
    The 39th Annual AAAI Conference on Artificial Intelligence (AAAI2025), フィラデルフィア，アメリカ，2025年2月．
  3. 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), ケープタウン，南アフリカ，2024年12月．
  4. 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), ケープタウン，南アフリカ，2024年12月．
  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), バルセロナ，スペイン，2023年7月．
  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), ローマ，イタリア，2023年5月．
  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), ホーボーケン，ニュージャージー州，アメリカ，2023年5月．
  8. 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), ハイブリッド開催（ソウル，韓国），2022年5月.
  9. 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), オンライン開催，2021年12月．
  10. Kengo Nakamura, Takeru Inoue, Masaaki Nishino, Norihito Yasuda:
    Efficient network reliability evaluation for client-server model.
    The 2021 IEEE Global Communications Conference (GLOBECOM2021), ハイブリッド開催（マドリード，スペイン），2021年12月．
  11. Kengo Nakamura, Shuhei Denzumi, Masaaki Nishino:
    Variable Shift SDD: a more succinct and canonical sentential decision diagram.
    The 18th Symposium on Experimental Algorithms (SEA2020), オンライン開催（カターニア，イタリア），2020年6月．
  12. 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), ニューヨーク，アメリカ，2020年2月．
  13. Kengo Nakamura:
    Fully dynamic connectivity oracles under general vertex updates.
    The 28th International Symposium on Algorithms and Computation (ISAAC2017), プーケット，タイ，2017年12月．
  14. 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), 新竹，台湾，2017年3月．

Domestic Talks

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

賞

  1. 人工知能学会 全国大会（第37回）優秀賞 (w/ 西野 正彬，湊 真一)．
    人工知能学会，2023年7月．
  2. NTTコミュニケーション科学基礎研究所 所長表彰（研究開発賞） (w/ 井上 武，西野 正彬，安田 宜仁)．
    NTTコミュニケーション科学基礎研究所，2023年4月．
  3. NTTコミュニケーション科学基礎研究所 所長表彰（奨励賞）．
    NTTコミュニケーション科学基礎研究所，2020年4月．
  4. 東京大学 情報理工学系研究科長賞．
    東京大学，2018年3月．
  5. ISAAC2017 Best Student Paper Award.
    The 28th International Symposium on Algorithms and Computation (ISAAC2017), 2017年12月．
  6. 東京大学 工学部長賞．
    東京大学，2016年3月．