Research
Publications
Kazuki Mitani, Takuya Mieno, Kazuhisa Seto, and Takashi Horiyama
Shortest cover after edit
[Conf] In Proceedings of the 35th Annual Symposium on Combinatorial Pattern Matching (CPM 2024), pages 24:1-24:15, June 2024 (Fukuoka, Japan)
[Preprint] arXiv:2402.17428, February 2024
Takashi Horiyama, Yasuaki Kobayashi, Hirotaka Ono, Kazuhisa Seto, and Ryu Suzuki
Theoretical Aspects of Generating Instances with Unique Solutions: Pre-assignment Models for Unique Vertex Cover
[Conf] In Proceedings of the 38th Annual AAAI Conference on Artificial Intelligence (AAAI 2024), Vol.38(18), pages 20726-20734, February 2024 (Vancouver, Canada)
[Preprint] arXiv:2312.10599, December 2023.
Yuki Kawakami, Shun Takahashi, Kazuhisa Seto, Takashi Horiyama, Yuki Kobayashi, Yuya Higashikawa, and Naoki Katoh
Lower Bounds for the Thickness and the Total Number of Edge Crossings of Euclidean Minimum Weight Laman Graphs and (2, 2)-Tight Graphs
[Journal] IEICE Transactions on Information and Systems, E107-D(6), pages 732-740, June 2024.
[Conf] In Proceedings of the 35th Canadian Conference on Computational Geometry (CCCG 2023), pages 191-196, August 2023 (Montreal, Canada)
Hideo Bannai, Mitsuru Funakoshi, Kazuhiro Kurita, Yuto Nakashima, Kazuhisa Seto, and Takeaki Uno
Optimal LZ-End Parsing is Hard
[Conf] In Proceedings of the 34th Annual Symposium on Combinatorial Pattern Matching (CPM 2023), LIPIcs 259, pages 3:1-3:11, June 2023 (Marne-la-Vallee, France)
[Preprint] arXiv:2302.02586, February 2022
Kazuki Mitani, Takuya Mieno, Kazuhisa Seto, and Takashi Horiyama
Finding top-k longest palindromes in substrings
[Journal] Theoretical Computer Science, Vol. 979, No. 114183, November 2023.
[Preprint] arXiv:2210.02000, October 2022
Kazuki Mitani, Takuya Mieno, Kazuhisa Seto, and Takashi Horiyama
Internal Longest Palindrome Queries in Optimal Time
[Conf.] In Proceedings of the 17th International Workshop on Algorithms and Computation (WALCOM 2023), LNCS 13973, pages 127-138, March 2023 (Hsinchu, Taiwan)
Tomu Makita, Atsuki Nagao, Tatsuki Okada, Kazuhisa Seto, and Junichi Teruyama
A Satisfiability Algorithm for Deterministic Width-2 Branching Programs
[Journal] IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences, E105-A(9), pages 1298-1308, Septmeber 2022.
Atsuki Nagao, Kazuhisa Seto, and Junichi Teruyama
Satisfiability Algorithm for Syntactic Read-k-times Branching Programs
[Journal] Theory of Computing Systems, Vol. 64(8), pages 1392-1407, November 2020 .
[Conf.] In Proceedings of the 28th International Symposium on Algorithms and Computation (ISAAC 2017), LIPIcs 92, pages 58:1-58:10, December 2017 (Phuket, Thailand)
Takayuki Sakai, Kazuhisa Seto, Suguru Tamaki, and Junichi Teruyama
Bounded Depth Circuits with Weighted Symmetric Gates: Satisfiability, Lower Bounds and Compression
[Journal] Journal of Computer and System Sciences, Vol. 105, pages 87-103, November 2019
[Conf.] In Proceedings of the 41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016), LIPIcs 58, pages 82:1-82:16, August 2016 (Krakow, Poland)
[Preprint] Electronic Colloquium on Computational Complexity, TR16-99, June 2016
Kazuhisa Seto and Junichi Teruyama
An Exact Algorithm for Oblivious Read-Twice Branching Program Satisfiability
[Journal] IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences, E99-A(6), pages 1019-1024, June 2016
Takayuki Sakai, Kazuhisa Seto, Suguru Tamaki, and Junichi Teruyama
Improved Exact Algorithms for Mildly Sparse Instances of Max SAT
[Journal] Theoretical Computer Science, Vol. 697, pages 58-68, October 2017
[Conf.] In Proceedings of the 10th International Symposium on Parameterized and Exact Computation (IPEC 2015), LIPIcs 43, pages 90-101, September 2015 (Patras, Greece)
Atsuki Nagao, Kazuhisa Seto, and Junichi Teruyama
A Moderately Exponential Time Algorithm for k-IBDD Satisfiability
[Journal] Algorithmica, Vol. 80(10), pages 2725-2741, October 2018
[Conf.] In Proceedings of the 14th Workshop on Algorithms and Data Structures (WADS 2015), LNCS 9214, pages 554-565, August 2015 (Victoria, Canada)
Kazuhisa Seto
An Introduction to Lower Bounds on Resolution Proof Systems
[Journal] Interdisciplinary Information Sciences, Vol. 21(4), pages 307-328, December, 2015
Takayuki Sakai, Kazuhisa Seto, and Suguru Tamaki
Solving Sparse Instances of Max SAT via Width Reduction and Greedy Restriction
[Journal] Theory of Computing Systems, Vol. 57(2), pages 426–443, August 2015
[Conf.] In Proceedings of the 17th International Conference on Theory and Applications of Satisfiability Testing (SAT 2014), LNCS 8561, pages 32-47, July 2014 (Vienna, Austria)
Atsuki Nagao, Kazuhisa Seto, and Junichi Teruyama
Efficient Algorithms for Sorting k-Sets in Bins
[Journal] IEICE Transactions on Information and Systems, E98-D(10), pages 1736-1743, October, 2015
[Conf.] In Proceedings of the 8th International Workshop on Algorithms and Computation (WALCOM 2014), LNCS 8344, pages 225-236, February 2014 (Chennai, India)
Kazuhisa Seto and Suguru Tamaki
A Satisfiability Algorithm and Average-Case Hardness for Formulas over the Full Binary Basis
[Journal] Computational Complexity (invited to special issue on CCC 2012), Vol. 22(2), pages 245–274, June 2013
[Conf.] In Proceedings of the 27th IEEE Conference on Computational Complexity (CCC 2012), pages 107-116, June 2012 (Porto, Portugal)
[Preprint] Electronic Colloquium on Computational Complexity, TR12-71, May 2012
Kazuo Iwama, Kazuhisa Seto, Tadashi Takai, and Suguru Tamaki
Improved Randomized Algorithms for 3-SAT
[Conf.] In Proceedings of the 21st International Symposium on Algorithms and Computation (ISAAC 2010), LNCS 6506, pages 73-82, December 2010 (Jeju, Korea)
Kazuo Iwama, Kazuhisa Seto, and Suguru Tamaki
The Planar Hajos Calculus for Bounded Degree Graphs
[Journal] IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences, E93-A(6), pages 1000-1007, June 2010
Kazuo Iwama, Kazuhisa Seto, and Suguru Tamaki
The Complexity of the Hajos Calculus for Planar Graphs
[Journal] Theoretical Computer Science, Vol. 411(7-9), pages 1182-1191, February 2010
Tutorial & Invited Talk
酒井 隆行,脊戸 和寿,玉置 卓
最大充足可能性問題の疎な例題に対する厳密アルゴリズム (依頼講演)
電子情報通信学会 総合大会 DS-1-5, 2014年3月 (新潟大学,新潟)
脊戸 和寿
回路から迫る P vs. NP (チュートリアル講演)
コンピューテーション研究会, 2013年12月 (沖縄産業支援センター, 沖縄)
Research Grants
研究代表者
2024年4月 〜 2028年3月 科学研究費助成事業 基盤研究 (B)
組合せ最適化問題に対する解の唯一化における計算複雑さの研究
2021年4月 〜 2024年3月 科学研究費助成事業 基盤研究 (C)
定数段数回路における計算限界導出技法の研究
2021年9月 〜 2023年3月 科学研究費助成事業 学術変革領域 (A) 公募研究
強指数時間仮説に基づく計算限界の理解と探求
2018年4月 〜 2021年3月(延長2022年3月) 科学研究費助成事業 基盤研究 (C)
強指数時間仮説の反証にむけた研究
2014年4月 〜 2017年3月 科学研究費助成事業 若手研究 (B)
回路計算量の下界証明におけるアルゴリズム的手法の研究
2010年8月 〜 2012年3月 科学研究費補助金 研究活動スタート支援
証明の複雑さにおけるグラフ理論的手法の構築
研究分担者
2022年4月 〜 2027年3月 科学研究費助成事業 基盤研究 (A) (代表:小野廣隆)
超スマート社会時代のアルゴリズム工学 - パラメータ化近似均衡計算
2022年4月 〜 2026年3月 科学研究費助成事業 基盤研究 (B) (代表:堀山貴史)
列挙や数え上げなどを統一的に扱うための基盤技術
2014年4月 〜 2017年3月 科学研究費補助金 新学術領域研究(領域代表:渡辺治、計画班代表:河原林健一)
多面的アプローチの統合による計算限界の解明 情報理論・符号理論からの計算限界解明
Talks (Only my own presentation)
Takashi Horiyama, Yasuaki Kobayashi, Hirotaka Ono, Kazuhisa Seto, and Ryu Suzuki
Exact Algorithms for Uniquifying Minimum Vertex Covers under Pre-assignment Models
電子情報通信学会コンピュテーション研究会, 信学技報, COMP2024-5, pages 10-13, 2024年5月 (京都大学, 京都)
脊戸 和寿
多数決関数の計算複雑さと未解決問題について
電子情報通信学会コンピュテーション研究会, 信学技報, COMP2022-30, page 48, 2022年12月 (愛媛大学, 愛媛)
Tomu Makita, Atsuki Nagao, Tatsuki Okada, Kazuhisa Seto, and Junichi Teruyama
A Moderately Exponential Time Satisfiability Algorithm for Linear-Sized Deterministic Width-2 Branching Programs
電子情報通信学会コンピュテーション研究会, 信学技報, COMP2022-14, pages 2-6, 2022年10月 (九州大学西新プラザ, 福岡)
清水 堅斗, 三觜 辰也, 脊戸 和寿
Sorting k-Sets in Bins問題に対する貪欲アルゴリズムの上界の改良
電子情報通信学会コンピュテーション研究会, 信学技報, vol. 116, no. 503, COMP2016-55, pages 29-32, 2017年3月 (名城大学, 愛知)
Kazuhisa Seto, Suguru Tamaki, and Junichi teruyama
An Exact Algorithm for the Satisfiability of Depth-2 SYM-AND Circuits
電子情報通信学会コンピュテーション研究会, 信学技報, vol. 116, no. 262, COMP2016-27, pages 29-34, 2016年10月 (東北大学, 宮城)
Kazuhisa Seto
Exact Algorithms for Max SAT
情報系 WINTER FESTA, ポスター, 2015年12月 (一橋講堂,東京)
Kazuhisa Seto
Approaches to Separate Complexity Classes
FIT2013(情報科学技術フォーラム), ポスター, 2013年9月 (鳥取大学,鳥取)
Takayuki Sakai, Kazuhisa Seto, and Suguru Tamaki
Solving Sparse Instances of Max SAT via Width Reduction and Greedy Restriction
Dagstulh Seminars 13331, August, 2013 (Saarland, Germany)
Kazuhisa Seto
A Satisfiability Algorithm and Average-Case Hardness for Formulas over the Full Binary Basis
コンピュテーション研究会, 2012年6月 (北海道大学, 北海道)
Kazuhisa Seto
Circuit Complexity : A Survey
Joint Workshop of Zhejiang Univ and Kyoto Univ on Algorithms and Combinatorial Mathematic, February, 2012 (Zhejiang University, China)
Kazuo Iwama, Kazuhisa Seto, and Suguru Tamaki
Enumerating Non-3-Colorable Graphs by the Hajos Calculus
Proc. the 3rd AAAC Annual Meeting (AAAC 2010), page 24, April, 2010 (Pohang, Korea)
Kazuo Iwama, Kazuhisa Seto, and Suguru Tamaki
Enumerating Non-3-colorable Planar Graphs by the Hajos Calculus
電子情報通信学会 総合大会 DS-1-4, 2010年3月 (東北大学,宮城)
Kazuo Iwama, Kazuhisa Seto, and Suguru Tamaki
Enumerating Non-3-colorable Planar Graphs by the Hajos Calculus
Proc. the 12th KOREA-JAPAN Joint Workshop on Algorithms and Computation (WAAC 2009), pages 14-21, July, 2009 (Soul, Korea)
Kazuo Iwama, Kazuhisa Seto, and Suguru Tamaki
The Planar Hajos Calculus for Bounded Degree Graphs
Proc. the 2nd AAAC Annual Meeting (AAAC 2009), page 29, April, 2009 (Hangzhou, China)
Kazuhisa Seto
The Planar Hajos Calculus for Bounded Degree Graphs
Joint Workshop of Beijing, Hong Kong and Kyoto on Computational Mathematics, Computer and System Sciences (CMCSS), March, 2009 (Kyoto University, Kyoto)
Takashi Horiyama, Kazuo Iwama, and Kazuhisa Seto
Constant Depth Circuits for Symmetric Boolean Functions
夏のLAシンポジウム,2006年8月 (広島大学,広島)
Thesis
Dissertation
On the Complexity of the Hajos Calculus for Planar Graphs
Master's Thesis
Constant Depth Circuits for Symmetric Boolean Functions
Bachelor's Thesis
段数を制限した論理回路の計算量について