Research
Papers
- 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)
- 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, 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, 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)
Surveys
- 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
Ph.D. Thesis
- Improved Algorithms for CNF Satisfiability Problems
School of Informatics, Kyoto University, March 2006
Supervisor: Prof. Kazuo Iwama