Suguru Tamaki

Most-cited papers

Improved upper bounds for 3-SAT
K. Iwama, Suguru Tamaki
2004ACM-SIAM Symposium on Discrete Algorithms125 citations
Semantic Scholar
Beating Brute Force for Systems of Polynomial Equations over Finite Fields
D. Lokshtanov, R. Paturi, Suguru Tamaki, Richard Ryan Williams +1 more
2017ACM-SIAM Symposium on Discrete Algorithms78 citations Open access
Semantic Scholar
Linear programming, width-1 CSPs, and robust satisfaction
G. Kun, R. O'Donnell, Suguru Tamaki, Yuichi Yoshida +1 more
2012Information Technology Convergence and Services71 citations Open access
Semantic Scholar
A satisfiability algorithm and average-case hardness for formulas over the full binary basis
Kazuhisa Seto, Suguru Tamaki
2012Computational Complexity52 citations Open access
Semantic Scholar
An exact algorithm for the Boolean connectivity problem for k-CNF
K. Makino, Suguru Tamaki, Masaki Yamamoto
2010Theoretical Computer Science30 citations Open access
Semantic Scholar
A Satisfiability Algorithm for Depth Two Circuits with a Sub-Quadratic Number of Symmetric and Threshold Gates
Suguru Tamaki
2016Electron. Colloquium Comput. Complex.27 citations
Semantic Scholar
Improved Randomized Algorithms for 3-SAT
K. Iwama, Kazuhisa Seto, Tadashi Takai, Suguru Tamaki
2010International Symposium on Algorithms and Computation23 citations
Semantic Scholar
MATHEMATICAL ENGINEERING TECHNICAL REPORTS On the Boolean Connectivity Problem for Horn Relations
K. Makino, Suguru Tamaki, Masaki Yamamoto
200723 citations
Semantic Scholar
Derandomizing the HSSW Algorithm for 3-SAT
K. Makino, Suguru Tamaki, Masaki Yamamoto
2011Algorithmica19 citations Open access
Semantic Scholar
Fine-grained quantum computational supremacy
T. Morimae, Suguru Tamaki
2019Quantum information & computation14 citations Open access
Semantic Scholar
A query efficient non‐adaptive long code test with perfect completeness
Suguru Tamaki, Yuichi Yoshida
2010Random Struct. Algorithms14 citations Open access
Semantic Scholar
Bounded Depth Circuits with Weighted Symmetric Gates: Satisfiability, Lower Bounds and Compression
Takayuki Sakai, Kazuhisa Seto, Suguru Tamaki, Junichi Teruyama
2019International Symposium on Mathematical Foundations of Computer Science13 citations Open access
Semantic Scholar
Circuit Size Lower Bounds and #SAT Upper Bounds Through a General Framework
Alexander Golovnev, A. Kulikov, A. Smal, Suguru Tamaki
2016International Symposium on Mathematical Foundations of Computer Science13 citations
Semantic Scholar
Derandomizing the HSSW Algorithm for 3-SAT
K. Makino, Suguru Tamaki, Masaki Yamamoto
2011Algorithmica11 citations Open access
Semantic Scholar
A Satisfiability Algorithm for Depth-2 Circuits with a Symmetric Gate at the Top and AND Gates at the Bottom
Takayuki Sakai, Kazuhisa Seto, Suguru Tamaki, Junichi Teruyama
2015Electron. Colloquium Comput. Complex.7 citations
Semantic Scholar
Solving Sparse Instances of Max SAT via Width Reduction and Greedy Restriction
Takayuki Sakai, Kazuhisa Seto, Suguru Tamaki
2014Theory of Computing Systems7 citations
Semantic Scholar
Quantum Query Complexity of Unitary Operator Discrimination
Akinori Kawachi, Ken'ichi Kawano, F. Le Gall, Suguru Tamaki
2017International Computing and Combinatorics Conference6 citations Open access
Semantic Scholar
Beating Brute Force for Systems of Polynomial Equations over Finite Fields
Lokshtanov Daniel, P. Ramamohan, Suguru Tamaki, W. Ryan +1 more
20176 citations
Semantic Scholar
The complexity of the Hajós calculus for planar graphs
K. Iwama, Kazuhisa Seto, Suguru Tamaki
2010Theoretical Computer Science6 citations Open access
Semantic Scholar
Additive-error fine-grained quantum supremacy
T. Morimae, Suguru Tamaki
2019Quantum5 citations Open access
Semantic Scholar
Improved exact algorithms for mildly sparse instances of Max SAT
Takayuki Sakai, Kazuhisa Seto, Suguru Tamaki, Junichi Teruyama
2017Theoretical Computer Science5 citations Open access
Semantic Scholar
Approximation Guarantees for the Minimum Linear Arrangement Problem by Higher Eigenvalues
Suguru Tamaki, Yuichi Yoshida
2018International Workshop and International Workshop on Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques3 citations
Semantic Scholar
Gate elimination: Circuit size lower bounds and #SAT upper bounds
Alexander Golovnev, A. Kulikov, A. Smal, Suguru Tamaki
2017Theoretical Computer Science3 citations Open access
Semantic Scholar
Exploiting partial knowledge of satisfying assignments
K. Iwama, Suguru Tamaki
2001Discrete Applied Mathematics3 citations Open access
Semantic Scholar
Fine-grained quantum supremacy based on Orthogonal Vectors, 3-SUM and All-Pairs Shortest Paths.
Ryunosuke Hayakawa, T. Morimae, Suguru Tamaki
20192 citations
Semantic Scholar
Parallel Repetition of Two-Prover One-Round Games: An Exposition
Suguru Tamaki
20152 citations Open access
Semantic Scholar
A Query Eﬃcient Non-Adaptive Long Code Test with Perfect Completeness
Suguru Tamaki, Yuichi Yoshida
2 citations
Semantic Scholar
Fine-grained quantum supremacy based on Orthogonal Vectors, 3-SUM and All-Pairs Shortest Paths
Ryunosuke Hayakawa, Morimae Tomoyuki, Suguru Tamaki
20191 citations
Semantic Scholar
An FPT Algorithm for Max-Cut Parameterized by Crossing Number
Yasuaki Kobayashi, Yusuke Kobayashi, S. Miyazaki, Suguru Tamaki
2019International Workshop on Combinatorial Algorithms1 citations
Semantic Scholar
Depth-scaling fine-grained quantum supremacy based on SETH and qubit-scaling fine-grained quantum supremacy based on Orthogonal Vectors and 3-SUM
T. Morimae, Suguru Tamaki
2019arXiv.org1 citations
Semantic Scholar
Robust Approximation of Temporal CSP
Suguru Tamaki, Yuichi Yoshida
2014Electron. Colloquium Comput. Complex.1 citations
Semantic Scholar
New Graph Calculi for Planar Non-3-Colorable Graphs
Youichi Hanatani, Takashi Horiyama, K. Iwama, Suguru Tamaki
2008IEICE Transactions on Fundamentals of Electronics Communications and Computer Sciences1 citations
Semantic Scholar
Fine-grained quantum computational supremacy
Morimae Tomoyuki, Suguru Tamaki
20190 citations
Semantic Scholar
On Computing a Center Persistence Diagram
Y. Higashikawa, N. Katoh, Guo-Hui Lin, Eiji Miyano +3 more
2019International Symposium on Fundamentals of Computation Theory0 citations Open access
Semantic Scholar
Local Restrictions from the Furst-Saxe-Sipser Paper
Suguru Tamaki, Osamu Watanabe
2016Theory of Computing Systems0 citations
Semantic Scholar
An Exact Algorithm for the Satisfiability of Depth-2 SYM-AND Circuits.
Kazuhisa Seto, Suguru Tamaki, Teruyama Junichi
20160 citations
Semantic Scholar
Introduction to Computational Complexity Theory (4): Barriers in Proving the Limits of Computation
Suguru Tamaki
20130 citations
Semantic Scholar
The Planar Hajós Calculus for Bounded Degree Graphs
K. Iwama, Kazuhisa Seto, Suguru Tamaki
2010IEICE Transactions on Fundamentals of Electronics Communications and Computer Sciences0 citations
Semantic Scholar
DS-1-4 Enumerating Non-3-colorable Planar Graphs by the Hajos Calculus
K. Iwama, Kazuhisa Seto, Suguru Tamaki
20100 citations
Semantic Scholar
An Improvement of the Soundness of a 3-bit PCP (Theoretical Computer Science and Its Applications)
Naoki Kinoshita, Suguru Tamaki, K. Iwama
20090 citations
Semantic Scholar
A Dichotomy Theorem within Schaefer for the Boolean Connectivity Problem
K. Makino, Suguru Tamaki, Masaki Yamamoto
2007Electron. Colloquium Comput. Complex.0 citations
Semantic Scholar
The Complexity of the Hajos Calculus on Planar Graphs
Hanatani Yoichi, Horiyama Takashi, K. Iwama, Suguru Tamaki
20070 citations
Semantic Scholar
Improved Algorithms for CNF Satisfiability Problems
Suguru Tamaki
20060 citations
Semantic Scholar
Increasing the Success Probability of PPSZ-type Satisfiability Testing
K. Iwama, Suguru Tamaki
20060 citations
Semantic Scholar