研究

論文

Tomoyuki Morimae and Suguru Tamaki
Depth-scaling fine-grained quantum supremacy based on SETH and qubit-scaling fine-grained quantum supremacy based on Orthogonal Vectors and 3-SUM
arXiv:1902.08382 [quant-ph], 2019
Tomoyuki Morimae and Suguru Tamaki
Fine-grained quantum computational supremacy
arXiv:1901.01637 [quant-ph], 2019
Suguru Tamaki
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
Akinori Kawachi, Kenichi Kawano, François Le Gall and Suguru Tamaki
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)
Suguru Tamaki and Yuichi Yoshida
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)
Alexander Golovnev, Alexander S. Kulikov, Alexander V. Smal and Suguru Tamaki
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'')
Takayuki Sakai, Kazuhisa Seto, Suguru Tamaki and Junichi Teruyama
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)
Daniel Lokshtanov, Ramamohan Paturi, Suguru Tamaki, Ryan Williams and Huacheng Yu
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)
Takayuki Sakai, Kazuhisa Seto, Suguru Tamaki and Junichi Teruyama
Bounded Depth Circuits with Weighted Symmetric Gates: Satisfiability, Lower Bounds and Compression
The 41st International Symposium on Mathematical Foundations of Computer Science (MFCS), pages 82:1--82:16, 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)
Takayuki Sakai, Kazuhisa Seto and Suguru Tamaki
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)
Suguru Tamaki and Yuichi Yoshida
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)
Suguru Tamaki and Yuichi Yoshida
Robust Approximation of Temporal CSP
The 17th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX), pages 419--432, September, 2014 (Barcelona, Spain)
Kazuhisa Makino, Suguru Tamaki and Masaki Yamamoto
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)
Kazuhisa Seto and Suguru Tamaki
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)
Gábor Kun, Ryan O'Donnell, Suguru Tamaki, Yuichi Yoshida and Yuan Zhou
Linear programming, width-1 CSPs, and robust satisfaction
The 3rd Innovations in Theoretical Computer Science Conference (ITCS), pages 484--495, January, 2012 (Massachusetts, USA)
Kazuhisa Makino, Suguru Tamaki and Masaki Yamamoto
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)
Kazuo Iwama, Kazuhisa Seto, Tadashi Takai and Suguru Tamaki
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)
Kazuhisa Makino, Suguru Tamaki and Masaki Yamamoto
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)
Kazuo Iwama, Kazuhisa Seto and Suguru Tamaki
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
Kazuo Iwama, Kazuhisa Seto and Suguru Tamaki
The Complexity of the Hajós Calculus for Planar Graphs
Theoretical Computer Science, 411(7-9):1182--1191, 2010
Youichi Hanatani, Takashi Horiyama, Kazuo Iwama and Suguru Tamaki
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
Kazuo Iwama and Suguru Tamaki
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)
Kazuo Iwama and Suguru Tamaki
Improved Upper Bounds for 3-SAT
The 15th annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 328--329, January, 2004 (New Orleans, USA)
Kazuo Iwama and Suguru Tamaki
Exploiting Partial Knowledge of Satisfying Assignments
The 5th Workshop on Algorithm Engineering (WAE), LNCS 2141, pages 118--128, August, 2001 (Aarhus, Denmark)

解説

Suguru Tamaki and Osamu Watanabe
Local Restrictions from the Furst-Saxe-Sipser Paper
Theory of Computing Systems, 60(1):20--32, 2017
Suguru Tamaki
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月号)

著書

伊藤大雄, 宇野裕之編著
離散数学のすすめ (玉置卓, 第16章計算量理論の最先端)
現代数学社, May, 2010

講演

玉置卓
精微な計算複雑性と暗号理論
第10回暗号及び情報セキュリティと数学の相関ワークショップ (CRISMATH 2018), December, 2018 (東京大学, 東京都文京区)
玉置卓
Fine-Grained Complexity and Cryptography: A Personal Survey
代数的手法による数理暗号解析に関する研究集会, February, 2018 (九州大学, 福岡市)
Suguru Tamaki
Beating Brute Force for Systems of Polynomial Equations over Finite Fields
ERATO感謝祭 Season IV, August, 2017 (国立情報学研究所, 東京都千代田区)
玉置卓
有限体上の多変数連立代数方程式系に対する総当り探索の打破
電子情報通信学会コンピュテーション研究会, March, 2017 (南山大学, 名古屋市)
Suguru Tamaki
Recent Developments on Circuit Satisfiability Algorithms
Fine-Grained Complexity and Algorithm Design Reunion, December, 2016 (Simons Institute, UC Berkeley, USA)
Suguru Tamaki
Recent Developments on Circuit Satisfiability Algorithms
Computational Complexity Conference (CCC) Satellite Tokyo Workshop, May, 2016 (学士会館, 東京都千代田区)
Suguru Tamaki
Faster Satisfiability Algorithms for Systems of Polynomial Equations over Finite Fields and ACC⁰[p]
Workshop on Satisfiability Lower Bounds and Tight Results for Parameterized and Exponential-Time Algorithms, November, 2015 (Simons Institute, UC Berkeley, USA)
Suguru Tamaki
Solving Systems of Polynomial Equations over GF(2) via Degree Reduction
Department of Computer Science Colloquium, October, 2015 (University of Nevada, Las Vegas, USA)
Suguru Tamaki
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)
Suguru Tamaki
The complexity of robust satisfiability of the constraint satisfaction problem
Dagstuhl Seminar 14201, May, 2014 (Schloss Dagstuhl, Germany)
玉置卓
計算複雑さへの招待 (4): 計算限界証明における障壁
電子情報通信学会コンピュテーション研究会, October, 2013 (名古屋工業大学, 名古屋市)
Suguru Tamaki
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 (京都大学, 京都市)

発表

Suguru Tamaki
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 (京都大学，京都市)
Suguru Tamaki
Beating Brute Force for Systems of Polynomial Equations over Finite Fields
情報系 WINTER FESTA, December, 2016 (国立情報学研究所, 東京都千代田区)
Kazuhisa Seto, Suguru Tamaki and Junichi Teruyama
An Exact Algorithm for the Satisfiability of Depth-2 SYM-AND Circuits
電子情報通信学会コンピュテーション研究会, October, 2016 (東北大学, 仙台市)
Suguru Tamaki
Satisfiability and Compression Algorithms for Bounded-Depth Circuits with Symmetric Gates
Fine Design seminar, October, 2015 (Simons Institute, UC Berkeley, USA)
Suguru Tamaki
Satisfiability Algorithms and Circuit Lower Bounds
Discrete Optimization Seminar, April, 2015 (京都大学, 京都市)
酒井隆行, 玉置卓
最大充足可能性問題の疎な例題に対する厳密アルゴリズムの改良
情報処理学会第77回全国大会, 6A-03, March, 2015 (京都大学, 京都市)
Suguru Tamaki
SAT Algorithms and Average Sensitivity
ELC Seminar, December, 2014 (東京工業大学, 東京都港区)
玉置卓
P vs. NP問題解決へのアプローチを整理しよう
ELC 平成26年度第2回領域会議, November, 2014 (九州大学, 福岡市)
Suguru Tamaki
On the complexity of randomness extractors
ELC Mini-Workshop on Boolean Functions, November, 2014 (東京工業大学, 東京都港区)
Takayuki Sakai, Kazuhisa Seto and Suguru Tamaki
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 (京都大学, 京都市)
Suguru Tamaki
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 (九州大学, 福岡市)
Kazuhisa Seto and Suguru Tamaki
A Satisfiability Algorithm for Formulas over the Full Binary Basis
RIMS研究集会「アルゴリズムと計算理論の新展開」(冬のLAシンポジウム)
予稿, pages 3-1--3-14, January, 2012 (京都大学，京都市)
玉置卓
研究のタネ: ○○ Complexity of △△ Complexity を研究するとよいかもしれない?
計算量理論若手の会, September, 2011 (那須郡)
Gábor Kun, Ryan O'Donnell, Suguru Tamaki, Yuichi Yoshida and Yuan Zhou
Linear Programming Robustly Decides Width-1 CSPs
2011年夏のLAシンポジウム, July, 2011 (THE VILLA HAMANAKO, 湖西市)
玉置卓
Satisfiability Algorithms/Long Code Test with Perfect Completeness
計算量理論若手の会, April, 2010 (京都大学, 京都市)
Kazuo Iwama, Tadashi Takai and Suguru Tamaki
Improved Randomized Algorithms for 3-SAT
The 3rd AAAC Annual Meeting
Proc. of AAAC 2010, p. 41, April, 2010 (Pohang, Korea)
Kazuo Iwama, Kazuhisa Seto and Suguru Tamaki
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)
Kazuhisa Seto, Suguru Tamaki and Kazuo Iwama
Enumerating Non-3-colorable Planar Graphs by the Hajós Calculus
電子情報通信学会総合大会 DS-1-4, March, 2010 (東北大学，仙台市)
高井唯史，玉置卓，岩間一雄
3-SAT ∈ RTIME(O(1.3211ⁿ))
RIMS研究集会「アルゴリズムと計算機科学の数理的基盤とその応用」(冬のLAシンポジウム)
予稿, pages 33-1--33-8, January, 2010 (京都大学，京都市)
Kazuo Iwama, Kazuhisa Seto and Suguru Tamaki
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)
Kazuo Iwama, Kazuhisa Seto and Suguru Tamaki
The Planar Hajós Calculus for Bounded Degree Graphs
The 2nd AAAC Annual Meeting
Proc. of AAAC 2009, p. 29, April, 2009 (Hangzhou, China)
Naoki Kinoshita, Suguru Tamaki and Kazuo Iwama
An Improvement of the Soundness of a 3-Bit PCP
RIMS研究集会「理論計算機科学の深化と応用」(冬のLAシンポジウム)
京都大学数理解析研究所講究録1649, pages 129--136, 2009 (京都大学，京都市)
Kazuo Iwama and Suguru Tamaki
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)
Youichi Hanatani, Takashi Horiyama, Kazuo Iwama and Suguru Tamaki
The Complexity of the Hajós Calculus on Planar Graphs
電子情報通信学会コンピュテーション研究会
信学技報，Vol.107, No.219, COMP2007-38, pages 43--50, September, 2007 (豊橋技術科学大学, 豊橋市)
Youichi Hanatani, Takashi Horiyama, Kazuo Iwama and Suguru Tamaki
The Complexity of the Hajós Calculus on Planar Graphs
2007年夏のLAシンポジウム
予稿, pages 8-1--8-20, July, 2007 (能登千里浜, 羽咋市)
Kazuo Iwama and Suguru Tamaki
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