Kengo Nakamura

Linguistic Intelligence Research Group
Innovative Communication Laboratory
NTT Communication Science Laboratories


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

Research Interests

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

Publication

  • Journal Paper
  • Conference Paper
  • Misc

Journal Paper

  1. Kengo Nakamura, Kunihiko Sadakane:
    Space-Efficient fully dynamic DFS in undirected graphs.
    Algorithms, Vol. 12(3), No. 52, 2019. [doi]

Conference Paper

  1. 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), to appear.
  2. Kengo Nakamura, Takeru Inoue, Masaaki Nishino, Norihito Yasuda:
    Efficient network reliability evaluation for client-server model.
    The 2021 IEEE Global Communications Conference (GLOBECOM2021), to appear.
  3. 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. [doi]
  4. 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. [doi]
  5. 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. [AAAI Digital Library]
  6. 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. [doi]
  7. 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. [doi]
  8. 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. [doi]
  9. 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. [doi]

Misc

  1. 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 [arXiv]
  2. 中村 健吾,伝住 周平,西野 正彬:
    変数シフトの導入による項分岐決定図の省空間化
    第11回データ工学と情報マネジメントに関するフォーラム (DEIM2019) 発表論文集, I1-4, 2019.
  3. 小林 尚輝,平尾 努,中村 健吾,上垣外 英剛,奥村 学,永田 昌明:
    テキストセグメンテーションによる教師なし修辞構造解析
    言語処理学会第25回年次大会 (NLP2019) 発表論文集, D5-3, 2019.
  4. 中村 健吾,定兼 邦彦:
    無向グラフ動的DFSに対する省空間かつ高速なアルゴリズム
    電子情報通信学会総合大会講演論文集,情報・システム講演論文集, pp. S-1--S-2, 2017.
  5. 中村 健吾,定兼 邦彦:
    無向グラフDFS木の動的更新アルゴリズムの省スペース化
    2016年度夏のLAシンポジウム, pp. 24-1--24-7, 2016.

Talk

  • International Talks
  • Domestic Talks

International Talks

  1. 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.
  2. 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.
  3. Kengo Nakamura:
    Fully dynamic connectivity oracles under general vertex updates.
    The 28th International Symposium on Algorithms and Computation (ISAAC2017), Phuket, Thailand, December 2017.
  4. 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. 中村 健吾,藤井 浩一,石橋 保身,神谷 俊介,梅谷 俊治:
    集合分割問題に対する重みつき局所探索法の改良
    RIMS研究集会「数理最適化の理論・アルゴリズム・応用」, Held online, August 2020.
  2. 中村 健吾,坂上 晋作,安田 宣仁:
    ZDDを用いた組合せ混雑ゲームの均衡計算.(poster)
    情報系 WINTER FESTA Episode 5 (理研AIP), Tokyo, December 2019.
  3. 中村 健吾,伝住 周平,西野 正彬:
    変数シフトの導入による項分岐決定図の省空間化
    第11回データ工学と情報マネジメントに関するフォーラム (DEIM2019), Sasebo (Nagasaki), March 2019.
  4. 中村 健吾
    頂点更新に対応した完全動的グラフ連結性オラクル.(poster)
    基盤(S)離散構造処理系プロジェクト 2017年度秋のワークショップ, Akkeshi (Hokkaido), November 2017.
  5. 中村 健吾,定兼 邦彦:
    無向グラフ動的DFSに対する省空間かつ高速なアルゴリズム
    COMP-ELC学生シンポジウム,電子情報通信学会総合大会, Nagoya, March 2017.
  6. 中村 健吾,定兼 邦彦:
    無向グラフDFS木の動的更新アルゴリズムの省空間化.(poster)
    情報系 WINTER FESTA Episode 2 (JST河原林ERATO), Tokyo, December 2016.
  7. 中村 健吾
    無向グラフ動的DFSの省空間実装について
    基盤(S)離散構造処理系プロジェクト 2016年度秋のワークショップ, Sapporo, November 2016.
  8. 中村 健吾,定兼 邦彦:
    無向グラフDFS木の動的更新アルゴリズムの省スペース化
    2016年度夏のLAシンポジウム, Heguri (Nara), July 2016.
  9. 中村 健吾,松尾 宇泰:
    重調和作用素の陽的なQTT分解とその応用
    「行列・固有値問題の解法とその応用」研究部会,日本応用数理学会 第12回研究部会連合発表会, Kobe, March 2016.

Awards

  1. NTTコミュニケーション科学基礎研究所 所長表彰(奨励賞)
    NTT Communication Science Laboratories, April 2020.
  2. 東京大学 情報理工学系研究科長賞
    The University of Tokyo, March 2018.
  3. ISAAC2017 Best Student Paper Award.
    The 28th International Symposium on Algorithms and Computation (ISAAC2017), December 2017.
  4. 東京大学 工学部長賞
    The University of Tokyo, March 2016.