脊戸和寿 (Kazuhisa Seto) - マイポータル

基本情報

所属: 北海道大学大学院情報科学研究院准教授

学位: 博士（情報学）(2010年3月京都大学)

J-GLOBAL ID: 201501014888315418
researchmap会員ID: B000243412

外部リンク: https://kaken.nii.ac.jp/d/r/20584056.ja.html

研究キーワード

研究分野

情報通信 / 情報学基礎論 /

経歴

2020年11月 - 現在

北海道大学, 大学院情報科学研究院, 准教授
2017年4月 - 2020年10月

成蹊大学, 理工学部, 准教授
2015年4月 - 2017年3月

成蹊大学, 理工学部, 専任講師
2013年9月 - 2015年3月

成蹊大学, 理工学部, 助教
2012年10月 - 2013年9月

電気通信大学, 大学院情報理工学研究科, 非常勤研究員
2010年4月 - 2012年9月

京都大学, 大学院情報学研究科, 特定研究員

論文

On the complexity of finding a spanning even tree in a graph.

Tesshu Hanaka, Yasuaki Kobayashi, Kazuhiro Kurita, Yasuko Matsui, Atsuki Nagao, Hirotaka Ono 0001, Kazuhisa Seto

CoRR abs/2412.17307 2024年
Shortest Cover After Edit.

Kazuki Mitani, Takuya Mieno, Kazuhisa Seto, Takashi Horiyama

CPM 24-15 2024年査読有り
Lower Bounds for the Thickness and the Total Number of Edge Crossings of Euclidean Minimum Weight Laman Graphs and (2,2)-Tight Graphs.

Yuki Kawakami, Shun Takahashi, Kazuhisa Seto, Takashi Horiyama, Yuki Kobayashi, Yuya Higashikawa, Naoki Katoh

IEICE Trans. Inf. Syst. 107(6) 732-740 2024年査読有り
Theoretical Aspects of Generating Instances with Unique Solutions: Pre-assignment Models for Unique Vertex Cover.

Takashi Horiyama, Yasuaki Kobayashi, Hirotaka Ono 0001, Kazuhisa Seto, Ryu Suzuki

AAAI 20726-20734 2024年査読有り
Finding top-k longest palindromes in substrings

Kazuki Mitani, Takuya Mieno, Kazuhisa Seto, Takashi Horiyama

Theoretical Computer Science 979 114183-114183 2023年9月査読有り
Lower Bounds for the Thickness and the Total Number of Edge Crossings of Euclidean Minimum Weight Laman Graphs and (2,2)-Tight Graphs.

Yuki Kawakami, Shun Takahashi, Kazuhisa Seto, Takashi Horiyama, Yuki Kobayashi, Yuya Higashikawa, Naoki Katoh

CCCG 191-196 2023年査読有り
Optimal LZ-End Parsing Is Hard.

Hideo Bannai, Mitsuru Funakoshi, Kazuhiro Kurita, Yuto Nakashima, Kazuhisa Seto, Takeaki Uno

34th Annual Symposium on Combinatorial Pattern Matching, CPM 2023, June 26-28, Marne-la-Vallée, France 3-11 2023年査読有り
A Satisfiability Algorithm for Deterministic Width-2 Branching Programs

MAKITA Tomu, NAGAO Atsuki, OKADA Tatsuki, SETO Kazuhisa, TERUYAMA Junichi

IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences E105.A(9) 1298-1308 2022年9月1日査読有り
Satisfiability Algorithm for Syntactic Read-k-times Branching Programs.

Atsuki Nagao, Kazuhisa Seto, Junichi Teruyama

Theory Comput. Syst. 64(8) 1392-1407 2020年査読有り
Bounded depth circuits with weighted symmetric gates: Satisfiability, lower bounds and compression

Takayuki Sakai, Kazuhisa Seto, Suguru Tamaki, Junichi Teruyama

Journal of Computer and System Sciences 105 87-103 2019年11月1日
A Moderately Exponential Time Algorithm for k-IBDD Satisfiability.

Atsuki Nagao, Kazuhisa Seto, Junichi Teruyama

Algorithmica 80(10) 2725-2741 2018年査読有り
Satisfiability Algorithm for Syntactic Read-$k$-times Branching Programs.

Atsuki Nagao, Kazuhisa Seto, Junichi Teruyama

28th International Symposium on Algorithms and Computation, ISAAC 2017, December 9-12, 2017, Phuket, Thailand 64(8) 58-10 2017年査読有り
Improved exact algorithms for mildly sparse instances of Max SAT.

Takayuki Sakai, Kazuhisa Seto, Suguru Tamaki, Junichi Teruyama

Theor. Comput. Sci. 697 58-68 2017年査読有り
Bounded Depth Circuits with Weighted Symmetric Gates: Satisfiability, Lower Bounds and Compression.

Takayuki Sakai, Kazuhisa Seto, Suguru Tamaki, Junichi Teruyama

J. Comput. Syst. Sci. 105 82-16 2016年査読有り
An Exact Algorithm for Oblivious Read-Twice Branching Program Satisfiability.

Kazuhisa Seto, Junichi Teruyama

IEICE Trans. Fundam. Electron. Commun. Comput. Sci. 99-A(6) 1019-1024 2016年査読有り
An introduction to lower bounds on resolution proof systems (Special issue: Reviews and lectures : exploring the limits of computation II)

Seto Kazuhisa

Interdisciplinary Information Sciences 21(4) 307-328 2015年12月査読有り
Improved Exact Algorithms for Mildly Sparse Instances of Max SAT.

Takayuki Sakai, Kazuhisa Seto, Suguru Tamaki, Junichi Teruyama

10th International Symposium on Parameterized and Exact Computation, IPEC 2015, September 16-18, 2015, Patras, Greece 43 90-101 2015年査読有り
Efficient Algorithms for Sorting k-Sets in Bins.

Atsuki Nagao, Kazuhisa Seto, Junichi Teruyama

IEICE Trans. Inf. Syst. 98-D(10) 1736-1743 2015年査読有り
A Moderately Exponential Time Algorithm for k-IBDD Satisfiability.

Atsuki Nagao, Kazuhisa Seto, Junichi Teruyama

Algorithms and Data Structures - 14th International Symposium, WADS 2015, Victoria, BC, Canada, August 5-7, 2015. Proceedings 9214 554-565 2015年査読有り
Solving Sparse Instances of Max SAT via Width Reduction and Greedy Restriction.

Takayuki Sakai, Kazuhisa Seto, Suguru Tamaki

Theory Comput. Syst. 57(2) 426-443 2015年査読有り

もっとみる

MISC

Optimal LZ-End Parsing is Hard.

Hideo Bannai, Mitsuru Funakoshi, Kazuhiro Kurita, Yuto Nakashima, Kazuhisa Seto, Takeaki Uno

CoRR abs/2302.02586 2023年
Internal Longest Palindrome Queries in Optimal Time.

Kazuki Mitani, Takuya Mieno, Kazuhisa Seto, Takashi Horiyama

CoRR abs/2210.02000 127-138 2022年
理工学部初年次学生に対するオンデマンド型online講義による情報関連講義の教育効果—Effectiveness of an On-demand Online Course in Information Science for First-year Science and Engineering Students

井内勝哉, 西尾悠, 脊戸和寿, 小川隆申

リメディアル教育研究 / リメディアル教育研究編集委員会 16(25) 161-167 2022年
コンピュテーション研究会近況報告

脊戸和寿

情報・システムソサイエティ誌 23(3) 8-9 2018年11月1日
Sorting k-Sets in Bins問題に対する貪欲アルゴリズムの上界の改良 (コンピュテーション)

清水堅斗, 三觜辰也, 脊戸和寿

電子情報通信学会技術研究報告 = IEICE technical report : 信学技報 116(503) 29-32 2017年3月7日
SYM-AND2段回路の充足可能性問題に対する厳密アルゴリズム

脊戸和寿, 玉置卓, 照山順一

電子情報通信学会技術研究報告 = IEICE technical report : 信学技報 116(262) 29-34 2016年10月21日
線形サイズk‐IBDD充足可能性問題に対する厳密アルゴリズム

脊戸和寿, 照山順一, 照山順一, 長尾篤樹, 長尾篤樹

情報処理学会研究報告(Web) 2015(AL-152) VOL.2015-AL-152,NO.1 (WEB ONLY) 2015年2月24日
線形サイズk-IBDD充足可能性問題に対する厳密アルゴリズム

脊戸和寿, 照山順一, 長尾篤樹

研究報告アルゴリズム（AL） 2015(1) 1-7 2015年2月24日
最大充足可能性問題の疎な例題に対する厳密アルゴリズム

脊戸和寿

成けい大学理工学研究報告 51(2) 19-21 2014年12月1日
k‐IBDD充足可能性問題に対する厳密アルゴリズム

脊戸和寿, 照山順一, 長尾篤樹

情報処理学会研究報告(Web) 2014(AL-149) VOL.2014-AL-149,NO.9 (WEB ONLY)-6 2014年9月5日
k-IBDD充足可能性問題に対する厳密アルゴリズム

脊戸和寿, 照山順一, 長尾篤樹

情報処理学会研究報告. AL, アルゴリズム研究会報告 2014(9) 1-6 2014年9月5日
最大充足可能性問題の疎な例題に対する厳密アルゴリズム

酒井隆行, 脊戸和寿, 玉置卓

電子情報通信学会大会講演論文集(CD-ROM) 2014(1) ROMBUNNO.DS-1-5-9"-"S-10" 2014年3月4日
DS-1-5 最大充足可能性問題の疎な例題に対する厳密アルゴリズム(DS-1.COMP-ELC学生シンポジウム,シンポジウムセッション)

酒井隆行, 脊戸和寿, 玉置卓

電子情報通信学会総合大会講演論文集 2014(1) "S-9"-"S-10" 2014年3月4日
計算複雑さへの招待(5) : 回路から迫るP vs. NP

脊戸和寿

電子情報通信学会技術研究報告. COMP, コンピュテーション 113(371) 57-57 2013年12月13日
k集合整列問題に対する効率のよいアルゴリズム

脊戸和寿, 照山順一, 長尾篤樹

電子情報通信学会技術研究報告. COMP, コンピュテーション 113(371) 81-85 2013年12月13日
DS-1-4 Enumerating Non-3-colorable Planar Graphs by the Hajos Calculus

Iwama Kazuo, Seto Kazuhisa, Tamaki Suguru

電子情報通信学会総合大会講演論文集 2010(1) "S-7"-"S-8" 2010年3月2日

講演・口頭発表等

多数決関数の計算複雑さと未解決問題について

脊戸和寿

電子情報通信学会コンピュテーション研究会 2022年12月6日
A Moderately Exponential Time Satisfiability Algorithm for Linear-Sized Deterministic Width-2 Branching Programs

Tomu Makita, Atsuki Nagao, Tatsuki Okada, Kazuhisa Seto, Junichi Teruyama

電子情報通信学会コンピュテーション研究会 2022年10月26日

所属学協会

電子情報通信学会

共同研究・競争的資金等の研究課題

組合せ最適化問題に対する解の唯一化における計算複雑さの研究

日本学術振興会科学研究費助成事業基盤研究(B) 2024年4月 - 2028年3月

脊戸和寿, 小野廣隆, 長尾篤樹
超スマート社会時代のアルゴリズム工学 - パラメータ化近似均衡計算

日本学術振興会科学研究費助成事業基盤研究(A) 基盤研究(A) 2022年4月 - 2027年3月

小野廣隆, 柳浦睦憲, 大舘陽太, 脊戸和寿, 土中哲秀
列挙や数え上げなどを統一的に扱うための基盤技術

日本学術振興会科学研究費助成事業基盤研究(B) 2022年4月 - 2026年3月

堀山貴史, 伝住周平, 和佐州洋, 栗田和宏, 脊戸和寿, 中畑裕
列挙や数え上げなどを統一的に扱うための基盤技術

日本学術振興会科学研究費助成事業基盤研究(B) 基盤研究(B) 2022年4月 - 2026年3月

堀山貴史, 伝住周平, 和佐州洋, 栗田和宏, 脊戸和寿, 中畑裕
定数段数回路における計算限界導出技法の研究

日本学術振興会科学研究費助成事業基盤研究(C) 基盤研究(C) 2021年4月 - 2024年3月

脊戸和寿
強指数時間仮説に基づく計算限界の理解と探究

日本学術振興会科学研究費助成事業学術変革領域研究(A) 学術変革領域研究(A) 2021年9月 - 2023年3月

脊戸和寿
強指数時間仮説の反証にむけた研究

日本学術振興会科学研究費助成事業基盤研究(C) 基盤研究(C) 2018年4月 - 2021年3月

脊戸和寿, 長尾篤樹
回路計算量の下界証明におけるアルゴリズム的手法の研究

日本学術振興会科学研究費助成事業若手研究(B) 若手研究(B) 2014年4月 - 2017年3月

脊戸和寿
情報理論・符号理論からの計算限界研究

日本学術振興会科学研究費助成事業新学術領域研究(研究領域提案型) 新学術領域研究(研究領域提案型) 2012年6月 - 2017年3月

河原林健一, 脊戸和寿, 玉置卓, 伊藤大雄, 吉田悠一
データの巨大化から生じる不完全情報への対処に主眼をおいた近似計算

日本学術振興会科学研究費助成事業基盤研究(A) 基盤研究(A) 2013年4月 - 2016年3月

岩間一雄, エイビスデイビッド, 宮崎修一, 玉置卓, 伊藤大雄, 堀山貴史, 吉田悠一, 岡本和也, 脊戸和寿, 川原純, 上野賢哉
証明の複雑さにおけるグラフ理論的手法の構築

日本学術振興会科学研究費助成事業研究活動スタート支援研究活動スタート支援 2010年 - 2011年

脊戸和寿

脊戸和寿

基本情報

研究キーワード

研究分野

経歴

論文

MISC

講演・口頭発表等

所属学協会

共同研究・競争的資金等の研究課題

メニュー

共著者の一覧