京都大学数理解析研究所RIMS共同研究（公開型）
「アルゴリズムと計算理論の新潮流」（研究代表者: 酒井 正彦）
2020年2月5日(水)〜2月7日(金)
一般セッション25分（発表20分，質疑5分）
学生セッション15分（発表12分，質疑3分）
○：発表者
◎：発表者（学生発表論文賞対象者）
京都大学数理解析研究所RIMS共同研究（公開型）
|
|
| [1] |
すべての通信路が敵に支配されてもゲーム理論的には安全な通信ができる
○ 安永 憲司 (大阪大学), 小柴 健史 (早稲田大学) |
| [2] |
カードを用いた安全な等号関数プロトコル
◎ スティールワングウィセス, 伊東 利哉 (東京工業大学) |
| [3] |
Private Simultaneous Messages および Conditional Disclosure of Secrets に関する情報理論的下界
○ 河内 亮周 (三重大学), 吉田 真紀 (情報通信研究機構) |
| [4] |
定数ファンインの対数深さ回路における暗号
◎ 江頭 昌平 (東京工業大学), Yuyu Wang (University of Electronic Science and Technology of China), 田中 圭介 (東京工業大学) |
| [5] |
小脳タンデム内部モデルの計算原理
○ 本多 武尊 (公益財団法人東京都医学総合研究所) |
| [S1] |
疎グラフにおけるヘドニックゲームの計算量
◎ 前井 康秀, 木谷 裕紀 (名古屋大学), 土中 哲秀 (中央大学), 小野廣隆 (名古屋大学) |
| [S2] |
コーダルグラフ関連クラスにおける2人プレイヤー拡散競争ゲームのナッシュ均衡
◎ 福薗 菜央佳, 木谷 裕紀 (名古屋大学), 土中 哲秀 (中央大学), 小野 廣隆 (名古屋大学) |
| [S3] |
セルオートマトンのプライマリーな局所規則
◎ 粉川 竜治, 藤尾 光彦 (近畿大学) |
| [S4] |
Moon-or-Sun, Nagareru, and Nurimeizu are NP-complete
◎ 井出達也, 岩本宙造 (広島大学) |
| [S5] |
Time Bound of Basic Steepest Descent Algorithm for M-convex Function Minimization
◎ 南川 智都, 塩浦 昭義 (東京工業大学) |
| [S6] |
多数決関数を計算する２段の多数決回路における総入次数の上下界
◎ 横川 拓哉, 尾島 康浩, 天野 一幸 (群馬大学) |
| [6] |
Computational complexity of the reconfiguration problem of integer linear systems
○ 木村 慧 (埼玉大学), 鈴木 顕 (東北大学) |
| [7] |
A refinement of Bell's inequality vs. quantum mechanics argument by algorithmic randomness
○ 只木孝太郎 (中部大学) |
| [8] |
Formally verified computable analysis and exact real computation
Michal Konečný (Aston University), Florian Steinberg (INRIA, Saclay), ○ ティース ホルガー (九州大学) |
| [9] |
ホワイトリスト順序問題の計算困難性
○ 原田 崇司 (高知工科大学), 田中 賢 (神奈川大学), 三河 賢治 (新潟大学) |
| [10] |
連結かつ非交差な幾何グラフの列挙，ランダム生成，最適化
◎ 中畑 裕 (京都大学), 堀山 貴史 (北海道大学), 湊 真一 (京都大学), 山中 克久 (岩手大学) |
| [11] |
パフィアンペアに対する一般化行列木定理
◎ 大城 泰平 (東京大学) |
| [12] |
SETHの下での完全二部グラフ数え上げの平均計算量
◎ 清水 伸高 (東京大学大学院 情報理工学系研究科), 平原 秀一 (国立情報学研究所) |
| [13] |
Computational Complexity of the Chromatic Art Gallery Problem for Orthogonal Polygons
○ 岩本宙造, 指宿竜明 (広島大学) |
| [14] |
被覆関係にある極小セパレータについて
○ 山﨑浩一 (群馬大学) |
| [15] |
グラフの極小多分割カットの効率よい列挙
◎ 栗田和宏 (北海道大学), 小林靖明 (京都大学) |
| [16] |
Packing disjoint A-paths with fixed length
Rémy Belmonte (電気通信大学), 土中 哲秀 (中央大学), ◎ 神崎 勝彰 (熊本大学), 清見 礼 (横浜市立大学), 小林 靖明, 小林 佑輔 (京都大学), Michael Lampis (Universite Paris Dauphine), 小野 廣隆 (名古屋大学), 大舘 陽太 (熊本大学) |
| [S7] |
二等辺三角形からのロボット避難問題
◎ 平尾 圭児, 藤原 洋志, 山本 博章 (信州大学) |
| [S8] |
ZDD圧縮データ上のマージン最大化
◎ 黒河 祐太, 畑埜 晃平, 瀧本 英二 (九州大学) |
| [S9] |
線形計画法による最適オンラインビンパッキングアルゴリズムの設計
◎ 滝澤 大生, 藤原 洋志, 山本 博章 (信州大学) |
| [S10] |
Graph partitioning problems parameterized by vertex integrity
◎ 儀間 達也 (熊本大学), 土中 哲秀 (中央大学), 清見 礼 (横浜市立大学), 小林 靖明 (京都大学), 大舘 陽太 (熊本大学) |
| [17] |
オラクルモデルを用いた不完全情報単貧民の解析
◎ 木谷 裕紀 (名古屋大学), 大渡 勝己 (フリー), 小野 廣隆 (名古屋大学) |
| [18] |
An Envy-free and Truthful Mechanism for the Cake-cutting Problem
○ Takao Asano, Hiroyuki Umeda (Chuo University) |
| [19] |
個体群プロトコルモデルにおける時間最適リーダ選挙
○ 首藤裕一 (大阪大学), 大下福仁 (奈良先端科学技術大学院大学), 泉泰介 (名古屋工業大学), 角川裕次 (龍谷大学), 増澤利光 (大阪大学) |
| [20] |
無記憶な非同期ロボット群による平面形成
○ 山内 由紀子 (九州大学) |
| [S11] |
On the regularity preservation property of register pushdown systems
◎ 仙田 涼摩 (名古屋大学), 高田 喜朗 (高知工科大学), 関 浩之 (名古屋大学) |
| [S12] |
Lazy Abstractionと精練を用いた組込みアセンブリプログラムのリアルタイム性のソフトウェアモデル検査
◎ 上出 浩夢, 山根 智 (金沢大学) |
| [S13] |
文字列の被覆配列を求める問題の一般化とその解法
◎ 菊池なつみ, ディプタラマ ヘンリアン, 吉仲亮, 篠原歩 (東北大学大学院情報科学研究科) |
| [S14] |
重複無し最長共通部分列問題の厳密アルゴリズム
◎ 歌島侃勇 (九州工業大学), 朝廣雄一 (九州産業大学), ジャンソン ジェスパー (香港理工大學), リン グオフイ (アルバータ大学), 宮野英次 (九州工業大学), 小野廣隆 (名古屋大学) |
| [S15] |
ランダム関数におけるk-XOR問題の量子アルゴリズム
◎ 中川 毅紀, 森 立平 (東京工業大学) |
| [21] |
Efficient Algorithm for Dodecahedron Folding
◎ 鎌田 斗南, 上原 隆平 (北陸先端科学技術大学院大学), 堀山 貴史 (北海道大学) |
| [22] |
順序保存パターン照合のための並列アルゴリズム
◎ ジャルガルサイハン ダワージャブ, ヘンドリアン ディプタラマ, 吉仲 亮, 篠原 歩 (東北大学大学院情報科学研究科) |
| [23] |
部分文字列同士の最長共通部分列長データ構造
○ 酒井義文 (東北大学) |
| [24] |
パラメタ化パターン照合のための索引グラフ構造
◎ 中島 克仁 (東北大学), 藤里 法輝 (九州大学), ディプタラマ ヘンリアン (東北大学), 中島 祐人 (九州大学), 吉仲 亮 (東北大学), 稲永 俊介, 坂内 英夫 (九州大学), 篠原 歩 (東北大学), 竹田 正幸 (九州大学) |
| [25] |
畳み込み和ならびにビット並列を用いた縦読みパターン照合
◎ 舩越 満, 中島 祐人, 稲永 俊介, 坂内 英夫, 竹田 正幸 (九州大学) |
| [26] |
複数テキスト索引構造のオンライン構築
高木 拓也 (富士通研究所), ○ 稲永 俊介 (九州大学), 有村 博紀 (北海道大学), Dany Breslauer (無所属), Diptarama Hendrian (東北大学) |