Harry Buhrman, Sevag Gharibian, Zeph Landau, François Le Gall, Norbert Schuch and Suguru Tamaki
A Simpler Approximation Algorithm for MAX-k-SAT
The 9th SIAM Symposium on Simplicity in Algorithms (SOSA), 2026, to appear (Vancouver, Canada)
Harry Buhrman, Sevag Gharibian, Zeph Landau, François Le Gall, Norbert Schuch and Suguru Tamaki
Beating the natural Grover bound for low-energy estimation and state preparation
Physical Review Letters, 135(3):030601, 2025
The 28th Quantum Information Processing conference (QIP), 2025 (Raleigh, North Carolina, USA)
(conference version: ``Beating Grover search for low-energy estimation and state preparation'')
Suguru Tamaki
A Satisfiability Algorithm for Depth Two Circuits with a Sub-Quadratic Number of Symmetric and Threshold Gates
Algorithmic Foundations for Social Advancement: Recent Progress on Theory and Practice, pages 307--326, Springer, 2025
Yuya Higashikawa, Naoki Katoh, Guohui Lin, Eiji Miyano, Suguru Tamaki, Junichi Teruyama and Binhai Zhu
On Computing a Center Persistence Diagram
The 24th International Symposium on Fundamentals of Computation Theory (FCT), pages 262--275, September 2023 (Trier, Germany)
Tomoyuki Morimae and Suguru Tamaki
Additive-error fine-grained quantum supremacy
Quantum, 4(329):1--12, 2020
Tomoyuki Morimae and Suguru Tamaki
Fine-grained quantum computational supremacy
Quantum Information & Computation, 19(13&14):1089--1115, 2019
Takayuki Sakai, Kazuhisa Seto, Suguru Tamaki and Junichi Teruyama
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)
Yasuaki Kobayashi, Yusuke Kobayashi, Shuichi Miyazaki and Suguru Tamaki
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
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)
Suguru Tamaki
Parallel Repetition of Two Prover One Round Games: An Exposition
Interdisciplinary Information Sciences, 21(4):289--306, 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, 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, K.Seto, T. 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
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 (WAAC), pages 14--21, July 2009 (Kookmin University, Seoul, Korea)
Naoki Kinoshita, Suguru Tamaki and Kazuo Iwama
An Improvement of the Soundness of a 3-Bit PCP
Theoretical Computer Science and its Applications, RIMS Kôkyûroku No. 1649, pages 129--136, 2009
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)
Ryu Hayakawa, Tomoyuki Morimae and Suguru Tamaki
Fine-grained quantum supremacy based on Orthogonal Vectors, 3-SUM and All-Pairs Shortest Paths
arXiv:1902.08382 [quant-ph], 2019
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
Improved Algorithms for CNF Satisfiability Problems
Graduate School of Informatics, Kyoto University, March 2006
Supervisor: Prof. Kazuo Iwama