研究

論文

On Computing a Center Persistence Diagram

The 24th International Symposium on Fundamentals of Computation Theory (FCT), pages 262-275, September 2023 (Trier, Germany)

Additive-error fine-grained quantum supremacy 

Quantum, 4(329):1--12, 2020

Fine-grained quantum computational supremacy

Quantum Information & Computation, 19(13&14):1089--1115, 2019

Bounded Depth Circuits with Weighted Symmetric Gates: Satisfiability, Lower Bounds and Compression

• Journal of Computer and System Sciences, 105:87--103, 2019

• The 41st International Symposium on Mathematical Foundations of Computer Science (MFCS), August, 2016 (Krakow, Poland)

(subsumes the technical report ``A Satisfiability Algorithm for Depth-2 Circuits with a Symmetric Gate at the Top and AND Gates at the Bottom,'' Electronic Colloquium on Computational Complexity (ECCC), TR15-136, 2015)

An Improved Fixed-Parameter Algorithm for Max-Cut Parameterized by Crossing Number

The 30th International Workshop on Combinatorial Algorithms (IWOCA), pages  327--338, July, 2019 (Pisa, Italy) Best Paper Award

Quantum Query Complexity of Unitary Operator Discrimination

• IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences, E102-D(3):483--491, 2019

• The 23rd Annual International Computing and Combinatorics Conference (COCOON), August, 2017 (Hong Kong, China)

Approximation Guarantees for the Minimum Linear Arrangement Problem by Higher Eigenvalues

• ACM Transactions on Algorithms, 14(4):45:1--45:13, 2018

• The 15th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX), August, 2012 (Massachusetts, USA)

Gate Elimination: Circuit Size Lower Bounds and #SAT Upper Bounds

• Theoretical Computer Science, 719:46--63, 2018

• The 41st International Symposium on Mathematical Foundations of Computer Science (MFCS), August, 2016 (Krakow, Poland)

(conference version: ``Circuit size lower bounds and #SAT upper bounds through a general framework'')

Improved Exact Algorithms for Mildly Sparse Instances of Max SAT

• Theoretical Computer Science, 697:58--68, 2017

• The 10th International Symposium on Parameterized and Exact Computation (IPEC), September, 2015 (Patras, Greece)

Beating Brute Force for Systems of Polynomial Equations over Finite Fields

The 28th ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 2190--2202, January, 2017 (Barcelona, Spain)

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

• Theory of Computing Systems, 57(2):426--443, 2015

• The 17th International Conference on Theory and Applications of Satisfiability Testing (SAT), July, 2014 (Vienna, Austria)

A Query Efficient Non-Adaptive Long Code Test with Perfect Completeness

• Random Structures & Algorithms, 47(2):386--406, 2015

• The 14th International Workshop on Randomized Techniques in Computation (RANDOM), September, 2010 (UPC Barcelona, Spain)

Robust Approximation of Temporal CSP

The 17th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX), pages 419--432, September, 2014 (Barcelona, Spain)

Derandomizing HSSW algorithm for 3-SAT

• Algorithmica, 67(2):112--124, 2013 (invited to special issue on COCOON 2011)

• The 17th Annual International Computing and Combinatorics Conference (COCOON), August, 2011 (Dallas, Texas, USA)

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

• Computational Complexity, 22(2):245--274, 2013 (invited to special issue on CCC 2012)

• The 27th IEEE Conference on Computational Complexity (CCC), June, 2012 (Porto, Portugal)

Linear programming, width-1 CSPs, and robust satisfaction

The 3rd Innovations in Theoretical Computer Science Conference (ITCS), pages 484--495, January, 2012 (Massachusetts, USA)

An Exact Algorithm for the Boolean Connectivity Problem for k-CNF

• Theoretical Computer Science, 412(35):4613--4618, 2011

• The 13th International Conference on Theory and Applications of Satisfiability Testing (SAT), July, 2010 (Edinburgh, Scotland)

Improved Randomized Algorithms for 3-SAT

The 21st International Symposium on Algorithms and Computation (ISAAC), LNCS 6506, pages 73--84, December, 2010 (Jeju Island, Korea)

On the Boolean Connectivity Problem for Horn Relations

• Discrete Applied Mathematics, 158(18):2024--2030, 2010

• The 10th International Conference on Theory and Applications of Satisfiability Testing (SAT), May, 2007 (Lisbon, Portugal)

The Planar Hajós Calculus for Bounded Degree Graphs

IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences, E93-A(6):1000--1007, 2010

The Complexity of the Hajós Calculus for Planar Graphs

Theoretical Computer Science, 411(7-9):1182--1191, 2010

New Graph Calculi for Planar Non-3-Colorable Graphs

IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences, E91-A(9):2301--2307, 2008

Exploiting Partial Knowledge of Satisfying Assignments

• Discrete Applied Mathematics, 155(12):1596--1603, 2007 (invited to special issue on SAT 2001)

• The 4th Workshop on Theory and Applications of Satisfiability Testing (SAT), June, 2001 (Boston, USA)

Improved Upper Bounds for 3-SAT

The 15th annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 328--329, January, 2004 (New Orleans, USA)

Exploiting Partial Knowledge of Satisfying Assignments

The 5th Workshop on Algorithm Engineering (WAE), LNCS 2141, pages 118--128, August, 2001 (Aarhus, Denmark)

プレプリント

Fine-grained quantum supremacy based on Orthogonal Vectors, 3-SUM and All-Pairs Shortest Paths

arXiv:1902.08382 [quant-ph], 2019

A Satisfiability Algorithm for Depth Two Circuits with a Sub-Quadratic Number of Symmetric and Threshold Gates

Electronic Colloquium on Computational Complexity (ECCC), TR16-100, 2016

解説

Local Restrictions from the Furst-Saxe-Sipser Paper

Theory of Computing Systems, 60(1):20--32, 2017

Parallel Repetition of Two Prover One Round Games: An Exposition

Interdisciplinary Information Sciences, 21(4):289--306, 2015

ネヴァンリンナ賞業績紹介 コート

数学セミナー, 54(1):48--53, 2015

メタアルゴリズムと計算限界証明の不思議な関係

電子情報通信学会誌, 96(9):679--682, 2013

確率的検査可能証明と近似不可能性

電子情報通信学会 知識ベース 6群2編7章2節

計算量理論の最先端

離散数学のすすめ11, 理系への数学, 41(2):49--53, 2008（2008年2月号)

著書

理論計算機科学事典 (玉置 卓, 3.5節 近似計算の理論)

朝倉書店, January, 2022

離散数学のすすめ (玉置 卓, 第16章 計算量理論の最先端)

現代数学社, May, 2010

講演

制約充足問題の研究: アルゴリズムと計算複雑性

第39回STクラブ, July, 2021 (じばさんびる, 姫路市)

SATの解空間連結性判定問題の計算複雑性について

組合せ遷移第12回セミナー・勉強会, June, 2021 (オンライン)

精微な計算複雑性と暗号理論

第10回暗号及び情報セキュリティと数学の相関ワークショップ (CRISMATH 2018), December, 2018 (東京大学, 東京都文京区)

Fine-Grained Complexity and Cryptography: A Personal Survey

代数的手法による数理暗号解析に関する研究集会, February, 2018 (九州大学, 福岡市)

Beating Brute Force for Systems of Polynomial Equations over Finite Fields

ERATO感謝祭 Season IV, August, 2017 (国立情報学研究所, 東京都千代田区)

有限体上の多変数連立代数方程式系に対する総当り探索の打破

電子情報通信学会コンピュテーション研究会, March, 2017 (南山大学, 名古屋市)

Recent Developments on Circuit Satisfiability Algorithms

Fine-Grained Complexity and Algorithm Design Reunion, December, 2016 (Simons Institute, UC Berkeley, USA)

Recent Developments on Circuit Satisfiability Algorithms

Computational Complexity Conference (CCC) Satellite Tokyo Workshop, May, 2016 (学士会館, 東京都千代田区)

Faster Satisfiability Algorithms for Systems of Polynomial Equations over Finite Fields and ACC0[p]

Workshop on Satisfiability Lower Bounds and Tight Results for Parameterized and Exponential-Time Algorithms, November, 2015 (Simons Institute, UC Berkeley, USA)

Solving Systems of Polynomial Equations over GF(2) via Degree Reduction

Department of Computer Science Colloquium, October, 2015 (University of Nevada, Las Vegas, USA)

Satisfiability Algorithms for Small Depth Circuits with Symmetric Gates

Workshop on Connections Between Algorithm Design and Complexity Theory, October, 2015 (Simons Institute, UC Berkeley, USA)

The complexity of robust satisfiability of the constraint satisfaction problem

Dagstuhl Seminar 14201, May, 2014 (Schloss Dagstuhl, Germany)

計算複雑さへの招待 (4): 計算限界証明における障壁

電子情報通信学会コンピュテーション研究会, October, 2013 (名古屋工業大学, 名古屋市)

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

Dagstuhl Seminar 13331, August, 2013 (Schloss Dagstuhl, Germany)

指数時間厳密アルゴリズム

学術情報メディアセンターセミナー 「アルゴリズムと計算量理論」, October, 2011 (京都大学, 京都市)

3SATに対する乱択アルゴリズムの改良

ERATO湊離散構造処理系＋NEO 合同研究会, July, 2010 (北海道大学, 札幌市)

Hajós Calculusの計算複雑さ

ワークショップ「離散アルゴリズムの最先端」, February, 2009 (東京工業大学, 東京都目黒区)

確率的証明の威力

情報学研究科通信情報システム専攻談話会, 2008年度第7回, December, 2008 (京都大学, 京都市)

3SATの計算時間について

京都大学 アルゴリズム・計算量・数理計画・OR・etc. 合同研究会, 第17回KIDS, April, 2004 (京都大学, 京都市)

発表

Max 𝑘-CSPの最適な近似(不)可能性証明の枠組みを 𝑘-Local Hamiltonian Problem (𝑘-LHP) に移植するための考察

量子計算資源量に制約がある量子計算のための理論基盤 ミーティング, March 2024 (名古屋大学, 名古屋市)

#SATアルゴリズムを用いた包除原理の高速化について

第二回AFSAコロキウム, June, 2022 (京都大学, 京都市)

通信複雑性とSATアルゴリズム

社会変革の源泉となる革新的アルゴリズム基盤の創出と体系化 (AFSA) 第2回領域集会, October, 2021 (オンライン)

有限体上の多変数連立代数方程式系に対する総当り探索の打破

兵庫県立大学 知の交流シンポジウム, September, 2021 (オンライン)

通信複雑性とSATアルゴリズム

社会変革の源泉となる革新的アルゴリズム基盤の創出と体系化 (AFSA) B04班セミナー, July, 2021 (オンライン)

OV仮定, 3-SUM仮定, APSP仮定に基づく精微な量子超越性

第1回量子ソフトウェア研究発表会, October, 2020 (オンライン)

精微な量子超越性の階層性定理

日本物理学会 2020年秋季大会, September, 2020 (オンライン)

Orthogonal Vectors, 3-SUM および All-Pairs Shortest Paths に基づく精微な量子超越性

量子情報技術研究会, November, 2019 (学習院大学, 東京都豊島区)

Orthogonal Vectors, 3-SUM および All-Pairs Shortest Paths に基づく精微な量子超越性

電子情報通信学会コンピュテーション研究会, October, 2019 (北海道大学, 札幌市)

精微な量子計算超越性

電子情報通信学会コンピュテーション研究会, September, 2019 (岡山大学, 岡山市)

Stabilizer rank: Sparse representation for classical simulation of quantum circuits

代数幾何学的計算理論とその周辺ミニワークショップ, August, 2019 (東京大学, 東京都目黒区)

Fine-grained量子スプレマシー

量子情報技術研究会 (QIT), May, 2019 (九州大学, 春日市)

Beating Brute Force for Systems of Polynomial Equations over Finite Fields

MPI-INF and MPI-MiS joint workshop on Theoretical Computer Science and Algebraic Geometry, January, 2019 (Saarbrücken, Germany)

複雑ネットワークに対する劣線形時間アルゴリズム研究の方向性+平均次数を近似する劣線形時間アルゴリズムの紹介

ABD14-UEC研究会, December, 2018 (電気通信大学, 調布市)

制約充足問題に対するアルゴリズム/(Fine-Grained) Complexity

科研費基盤 (S) 離散構造処理系プロジェクト 北大・京大研究交流会, October, 2018 (北海道大学, 札幌市)

定数次数グラフにおけるkモジュラリティ最大化問題のNP困難性

電子情報通信学会コンピュテーション研究会, September, 2018 (九州工業大学, 飯塚市)

複雑ネットワークは超有限?

ABD14-UEC研究会, July, 2018 (電気通信大学, 調布市)

ユニタリ演算識別問題の質問計算量

RIMS研究集会「理論計算機科学の最先端」(冬のLAシンポジウム), February, 2017 (京都大学，京都市)

Beating Brute Force for Systems of Polynomial Equations over Finite Fields

情報系 WINTER FESTA, December, 2016 (国立情報学研究所, 東京都千代田区)

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

電子情報通信学会コンピュテーション研究会, October, 2016 (東北大学, 仙台市)

Satisfiability and Compression Algorithms for Bounded-Depth Circuits with Symmetric Gates

Fine Design seminar, October, 2015 (Simons Institute, UC Berkeley, USA)

Satisfiability Algorithms and Circuit Lower Bounds

Discrete Optimization Seminar, April, 2015 (京都大学, 京都市)

最大充足可能性問題の疎な例題に対する厳密アルゴリズムの改良

情報処理学会 第77回全国大会, 6A-03, March, 2015 (京都大学, 京都市)

SAT Algorithms and Average Sensitivity

ELC Seminar, December, 2014 (東京工業大学, 東京都港区)

P vs. NP問題解決へのアプローチを整理しよう

ELC 平成26年度第2回領域会議, November, 2014 (九州大学, 福岡市)

On the complexity of randomness extractors

ELC Mini-Workshop on Boolean Functions, November, 2014 (東京工業大学, 東京都港区)

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

The 7th AAAC Annual Meeting

Proc. of AAAC 2014, May, 2014 (Hangzhou, China)

最大充足可能性問題の疎な例題に対する厳密アルゴリズム

電子情報通信学会 総合大会 DS-1-5, March, 2014 (新潟大学, 新潟市)

Parallel Repetition of Two Prover One Round Games

計算量理論若手の会, September, 2013 (米沢市)

最大充足可能性問題の疎な例題に対する厳密アルゴリズム

2013年夏のLAシンポジウム

予稿, pages 8-1--8-6, July, 2013 (志賀島, 福岡市)

メタアルゴリズムによる計算限界証明

ELC 平成25年度第1回領域会議, June, 2013 (京都大学, 京都市)

The complexity of robust satisfiability of the constraint satisfaction problem

The 6th AAAC Annual Meeting

Proc. of AAAC 2013, April, 2013 (Matsushima, Japan)

計算限界証明における障壁と性質検査アルゴリズム

ELC Mini-Workshop (A02), December, 2012 (東京工業大学, 東京都港区)

相対化不可能な証明手法

計算量理論若手の会, September, 2012 (九州大学, 福岡市)

A Satisfiability Algorithm for Formulas over the Full Binary Basis

RIMS研究集会「アルゴリズムと計算理論の新展開」(冬のLAシンポジウム)

予稿, pages 3-1--3-14, January, 2012 (京都大学，京都市)

研究のタネ: ○○ Complexity of △△ Complexity を研究するとよいかもしれない?

計算量理論若手の会, September, 2011 (那須郡)

Linear Programming Robustly Decides Width-1 CSPs

2011年夏のLAシンポジウム, July, 2011 (THE VILLA HAMANAKO, 湖西市)

Satisfiability Algorithms/Long Code Test with Perfect Completeness

計算量理論若手の会, April, 2010 (京都大学, 京都市)

Improved Randomized Algorithms for 3-SAT

The 3rd AAAC Annual Meeting

Proc. of AAAC 2010, p. 41, April, 2010 (Pohang, Korea)

Enumerating Non-3-colorable Planar Graphs by the Hajós Calculus

The 3rd AAAC Annual Meeting

Proc. of AAAC 2010, p. 24, April, 2010 (Pohang, Korea)

Enumerating Non-3-colorable Planar Graphs by the Hajós Calculus

電子情報通信学会 総合大会 DS-1-4, March, 2010 (東北大学，仙台市)

3-SAT ∈ RTIME(O(1.3211n))

RIMS研究集会「アルゴリズムと計算機科学の数理的基盤とその応用」(冬のLAシンポジウム)

予稿, pages 33-1--33-8, January, 2010 (京都大学，京都市)

Enumerating Non-3-colorable Planar Graphs by the Hajós Calculus

The 12th Korea-Japan Joint Workshop on Algorithms and Computation

Proc. of WAAC 2009, pages 14--21, July, 2009 (Kookmin University, Seoul, Korea)

The Planar Hajós Calculus for Bounded Degree Graphs

The 2nd AAAC Annual Meeting

Proc. of AAAC 2009, p. 29, April, 2009 (Hangzhou, China)

An Improvement of the Soundness of a 3-Bit PCP

RIMS研究集会「理論計算機科学の深化と応用」(冬のLAシンポジウム)

京都大学数理解析研究所講究録1649, pages 129--136, 2009 (京都大学，京都市)

The Complexity of the Hajós Calculus for Planar Graphs

The First AAAC Annual Meeting

Proc. of AAAC 2008, p. 65, April, 2008 (Pokfulam, Hong Kong)

The Complexity of the Hajós Calculus on Planar Graphs

電子情報通信学会コンピュテーション研究会

信学技報，Vol.107, No.219, COMP2007-38, pages 43--50, September, 2007 (豊橋技術科学大学, 豊橋市)

The Complexity of the Hajós Calculus on Planar Graphs

2007年夏のLAシンポジウム

予稿, pages 8-1--8-20, July, 2007 (能登千里浜, 羽咋市)

Increasing the Success Probability of PPSZ-type Satisfiability Testing

電子情報通信学会コンピュテーション研究会

信学技報，Vol.105, No.680, COMP2005-63, pages 1--6, March, 2006 (電気通信大学, 調布市)

3SATの計算時間の上限の改良について

2003年夏のLAシンポジウム

予稿, pages 29-1--29-3, July, 2003 (合歓の郷, 志摩市)

SAT充足解の偏りを利用した局所探索の高速化

電子情報通信学会コンピュテーション研究会

信学技報，Vol.101, No.44, COMP2001-5, pages 49--56, May, 2001 (名古屋大学, 名古屋市)

偏りのある充足解をもつSATに対する局所探索アルゴリズムの解析と応用

電子情報通信学会 総合大会2001 D-1-3, March, 2001 (立命館大学, 草津市)

学位論文

Improved Algorithms for CNF Satisfiability Problems

京都大学大学院情報学研究科, March, 2006

指導教員: 岩間 一雄 教授

プログラミングコンテスト

並列ソフトウエアコンテスト2000 (自由部門)

クラスA 2位, クラスB 2位, クラスC 5位, May, 2000