研究プロジェクト
渡辺研で現在行っている，あるいは少し以前に行われた研究プロジェクトをいくつか紹介します．
※お断り※ このページは，研究室のメンバーが時間のあるときに，適宜紹介を書き足すことで作られています．したがって，すべてのプロジェクトを列挙したものではありません．また，プロジェクトといっても学生 1 名が取り組んでいるものから，大規模な予算を獲得してやっているものまで未整理のまま載せています．あくまで例と思ってください．
「主要な研究テーマ」 の分類にしたがって大ざっぱに分けています．
内容項目
アルゴリズムの設計と解析
計算複雑さの理論
- 平面有向グラフ上の到達可能性問題の省スペースアルゴリズム (今井，中川，他, CCC 2013)
- 平面有向グラフ上の到達可能性問題に対する多項式時間かつ \(O(\sqrt{n})\) スペースアルゴリズム．
- ランダム制約充足問題の反駁問題に対する半正定値緩和の限界 (森，RANDOM 2016, STOC 2017)
- 与えられた3CNFが充足可能であることを証明するためには，充足解を導出すればよい． 一方で，与えられた3CNFが「充足不可能」であることを証明するためには，充足制約数最大化問題の半正定値緩和の双対解を導出すれば十分である． 十分制約の数が多いランダムな3CNFに対して，この半正定値緩和によって充足不可能性を証明をするためには 制約の数が \(n^{1.5}\) 以上必要であることを示した． 一方で先行研究では制約の数が \(n^{1.5}\log^c n\) あれば(\(c\) は定数)半正定値緩和によって充足不可能性が証明できることが示されているので，この結果はほぼタイトである． この結果は3CNFに限らず一般の\(k\)CSPに対しても有効である．