Research

Publications

Shortest cover after edit

[Conf] In Proceedings of the 35th Annual Symposium on Combinatorial Pattern Matching  (CPM 2024), to appear, June 2024 (Fukuoka, Japan)

[Preprint] arXiv:2402.17428, February 2024

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. 

Lower Bounds for the Thickness and the Total Number of Edge Crossings of Euclidean Minimum Weight Laman Graphs and (2, 2)-Tight Graphs

[Conf] In Proceedings of the 35th Canadian Conference on Computational Geometry (CCCG 2023), pages 191-196, August 2023 (Montreal, Canada)

[Journal] IEICE Transactions on Information and Systems, E107-D(6), to appear, June 2024.

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 

Finding top-k longest palindromes in substrings

[Journal] Theoretical Computer Science, Vol. 979, No. 114183,  November 2023.

[Preprint] arXiv:2210.02000, October 2022 

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)

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.

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)

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 

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 

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)

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)

An Introduction to Lower Bounds on Resolution Proof Systems

[Journal] Interdisciplinary Information Sciences, Vol. 21(4), pages 307-328, December, 2015

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)

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)

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 

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)

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

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

研究代表者

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

定数段数回路における計算限界導出技法の研究

強指数時間仮説に基づく計算限界の理解と探求

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

回路計算量の下界証明におけるアルゴリズム的手法の研究

証明の複雑さにおけるグラフ理論的手法の構築


研究分担者

超スマート社会時代のアルゴリズム工学 - パラメータ化近似均衡計算

列挙や数え上げなどを統一的に扱うための基盤技術

多面的アプローチの統合による計算限界の解明 情報理論・符号理論からの計算限界解明

Talks (Only my own presentation)

Exact Algorithms for Uniquifying Minimum Vertex Covers under Pre-assignment Models

電子情報通信学会コンピュテーション研究会, 信学技報, COMP2024-5, pages 10-13, 2024年5月 (京都大学, 京都)

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

電子情報通信学会コンピュテーション研究会, 信学技報, COMP2022-30, page 48, 2022年12月 (愛媛大学, 愛媛)

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月 (名城大学, 愛知)

An Exact Algorithm for the Satisfiability of Depth-2 SYM-AND Circuits

電子情報通信学会コンピュテーション研究会, 信学技報, vol. 116, no. 262, COMP2016-27, pages 29-34, 2016年10月 (東北大学, 宮城)

Exact Algorithms for Max SAT

情報系 WINTER FESTA, ポスター, 2015年12月 (一橋講堂，東京) 

Approaches to Separate Complexity Classes

FIT2013(情報科学技術フォーラム), ポスター, 2013年9月 (鳥取大学，鳥取) 

Solving Sparse Instances of Max SAT via Width Reduction and Greedy Restriction

Dagstulh Seminars 13331, August, 2013 (Saarland, Germany)

A Satisfiability Algorithm and Average-Case Hardness for Formulas over the Full Binary Basis

コンピュテーション研究会, 2012年6月 (北海道大学, 北海道) 

Circuit Complexity : A Survey 

Joint Workshop of Zhejiang Univ and Kyoto Univ on Algorithms and Combinatorial Mathematic, February, 2012 (Zhejiang University, China)

Enumerating Non-3-Colorable Graphs by the Hajos Calculus

Proc. the 3rd AAAC Annual Meeting (AAAC 2010), page 24, April, 2010 (Pohang, Korea) 

Enumerating Non-3-colorable Planar Graphs by the Hajos Calculus

電子情報通信学会 総合大会 DS-1-4, 2010年3月 (東北大学，宮城）

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)

The Planar Hajos Calculus for Bounded Degree Graphs

Proc. the 2nd AAAC Annual Meeting (AAAC 2009), page 29, April, 2009 (Hangzhou, China)

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)

Constant Depth Circuits for Symmetric Boolean Functions

夏のLAシンポジウム，2006年8月 (広島大学，広島）

Thesis

On the Complexity of the Hajos Calculus for Planar Graphs

Constant Depth Circuits for Symmetric Boolean Functions

段数を制限した論理回路の計算量について