イベント企画
トップコンファレンス 2 アルゴリズムとデータベース
8/25(水) 13:10-15:10
第4イベント会場(オンライン)
座長:天笠俊之(筑波大学)
座長補佐:大下 福仁(奈良先端科学技術大学院大学)
13:10-13:30 講演(1) 【タイトル邦題】 最悪時メタ計算量によるPHの平均時計算量の特徴付け
平原 秀一(国立情報学研究所 情報学プリンシプル研究系 助教)
【原発表の書誌情報】 S. Hirahara: Characterizing Average-Case Complexity of PH by Worst-Case Meta-Complexity, In Proceedings of the 61th IEEE Annual Symposium on Foundations of Computer Science (FOCS 2020), November 2020
【概要】 本研究では、PHの平均時計算量を時間制限付きコルモゴロフ記述量の最悪時メタ計算量の概念によって特徴付けを与える。この特徴付けは平均時計算量の新しい解析方法を与えており、特に系としてPHに関する困難性増幅定理を得る。すなわち、PHの入力のうち99%が計算困難であることと、PHの入力のうち1%が計算困難であることが同値であるということを示す。
【略歴】 2019年東京大学情報理工学系研究科博士課程修了。2019年より国立情報学研究所助教。
13:30-13:50 講演(2) 【タイトル邦題】 多様性最大部分グラフ探索アルゴリズム
土中 哲秀(名古屋大学 大学院情報学研究科数理情報学専攻 助教)
【原発表の書誌情報】 Tesshu Hanaka, Yasuaki Kobayashi, Kazuhiro Kurita, Yota Otachi. “Finding diverse trees, paths, and more”, Proceedings of the 35th AAAI Conference on Artificial Intelligence (AAAI 2021), 35(5), pp. 3778-3786, AAAI Press, 2021.
【概要】 数理モデリングは現実の問題を解くための標準的なアプローチであるが,数理モデル自体が近似的なものであり,解を1つ発見するだけでは不十分な場合も多く存在する.これに対して,本研究では,いくつかの基本的な問題において多様性を最大化する解集合を見つける固定パラメータ容易アルゴリズムを提案する.
【略歴】 2018年九州大学大学院経済学府経済工学専攻博士後期課程修了,博士(経済学).中央大学理工学部情報工学科を経て,現在,名古屋大学大学院情報学研究科数理情報学専攻助教.主にグラフアルゴリズムの研究に従事.
13:50-14:10 講演(3) 【タイトル邦題】 グラフアルゴリズムの平均感度
𠮷田 悠一(国立情報学研究所 )
【原発表の書誌情報】 Nithin Varma and Yuichi Yoshida. Average Sensitivity of Graph Algorithms. Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 684–703, 2021.
【概要】 グラフアルゴリズムを実問題に応用する際には、入力グラフに欠損があると考えるのが自然である。本研究では、欠損がある場合にどれだけ出力が変化するかを定式化した「アルゴリズムの平均感度」という概念を提唱し、その基本的な性質や具体的なグラフの問題に対する上下限について議論する。
【略歴】 2012年京都大学大学院情報学研究科修了。同年より国立情報学研究所特任助教。2015年より同准教授。数理的考察に基づく巨大データに対するアルゴリズムの研究に従事。
14:10-14:30 講演(4) 【タイトル邦題】 道路ネットワーク上の軌跡データに対する重み付き編集距離制約下の部分軌跡検索
小出 智士(豊田中央研究所 )
【原発表の書誌情報】 Koide, S., Xiao, C., Ishikawa, Y., Fast Subtrajectory Similarity Search in Road Networks under Weighted Edit Distance Constraints, Proceedings of the VLDB Endowment 13 (11), 2188-2201
【概要】 本研究では自動車などのネットワーク上の移動履歴が記号列データベースとして表現できることに着目した部分類似軌跡検索アルゴリズムを提案する。既知のEDRやERPなどの類似度指標を含む「重み付き編集距離」を用いた場合に適用可能ないくつかの技法を提案し,大幅な高速化を実現した。
【略歴】 2006年大阪大学大学院情報科学研究科博士前期課程修了。同年,株式会社豊田中央研究所入社。2020年名古屋大学大学院情報学研究科博士後期課程修了。空間データベース,機械学習などの研究に従事。
14:30-14:50 講演(5) 【タイトル邦題】 段階的学習を用いたプライバシ保護型深層生成モデル
高木 駿(京都大学 )
【原発表の書誌情報】 Takagi, S., Takahashi, T., Cao, Y., & Yoshikawa, M. (2021, April). P3GM: Private high-dimensional data release via privacy preserving phased generative model. In 2021 IEEE 37th International Conference on Data Engineering (ICDE) (pp. 169-180). IEEE.
【概要】 本研究では,差分プライバシによるプライバシ保護型深層生成モデルを考案する.既存研究では,差分プライバシに必要な雑音が原因で,生成データの質が悪くなってしまう.そこで,この研究では,雑音の影響を軽減した段階的な学習を行う新しい生成モデルP3GMを提案する.
【略歴】 2021年京都大学大学院情報学研究科博士前期課程修了.現在,同学博士後期課程在学.
14:50-15:10 講演(6) 【タイトル邦題】 スキル向上を可能とする推薦の実現に向けた行動系列におけるユーザ成長とアイテム難易度のモデル化
梅本 和俊(東京大学 生産技術研究所 助教)
【原発表の書誌情報】 Kazutoshi Umemoto, Tova Milo, and Masaru Kitsuregawa. Toward Recommendation for Upskilling: Modeling Skill Improvement and Item Difficulty in Action Sequences. In Proceedings of the 36th IEEE International Conference on Data Engineering (ICDE 2020), pp. 169-180, 2020.
【概要】 推薦アイテムを順に消費してもらうことでユーザのスキルを向上させることは可能だろうか?本研究では、そのような推薦システムの実現に向けて、一連の行動を通じたユーザの成長の過程を、各時点の行動において選択されるアイテムの難易度と紐付けてモデル化するという問題に取り組む。
【略歴】 2016年、京都大学大学院情報学研究科博士後期課程修了。博士(情報学)。同年より、情報通信研究機構ソーシャルビッグデータ研究連携センター研究員ならびに東京大学生産技術研究所特任助教。2020年より、東京大学生産技術研究所助教、現在に至る。専門分野は情報検索で、特に情報システムのユーザ行動の分析・モデル化・デザイン・活用に関する研究に従事。