Suguru Tamaki

56 papers A* 2A 5B 4C 1Misc 2Journal 36Unranked 6
YearRankTypeTitle / Venue / Authors
2026 — conf
A Simpler Exponential-Time Approximation Algorithm for MAX-k-SAT.
SOSA
Harry Buhrman, Sevag Gharibian, Zeph Landau, François Le Gall, Norbert Schuch, Suguru Tamaki
2025 J jnl
A Simpler Exponential-Time Approximation Algorithm for MAX-k-SAT.
CoRR
Harry Buhrman, Sevag Gharibian, Zeph Landau, François Le Gall, Norbert Schuch, Suguru Tamaki
2024 J jnl
Beating Grover search for low-energy estimation and state preparation.
CoRR
Harry Buhrman, Sevag Gharibian, Zeph Landau, François Le Gall, Norbert Schuch, Suguru Tamaki
2023 B conf
On Computing a Center Persistence Diagram.
FCT
Yuya Higashikawa, Naoki Katoh, Guohui Lin, Eiji Miyano, Suguru Tamaki, Junichi Teruyama, Binhai Zhu
2022 J jnl
Foreword.
IEICE Trans. Fundam. Electron. Commun. Comput. Sci.
Suguru Tamaki
2020 J jnl
Additive-error fine-grained quantum supremacy.
Quantum
Tomoyuki Morimae, Suguru Tamaki
2019 J jnl
An FPT Algorithm for Max-Cut Parameterized by Crossing Number.
CoRR
Yasuaki Kobayashi, Yusuke Kobayashi, Shuichi Miyazaki, Suguru Tamaki
2019 C conf
An Improved Fixed-Parameter Algorithm for Max-Cut Parameterized by Crossing Number.
IWOCA
Yasuaki Kobayashi, Yusuke Kobayashi, Shuichi Miyazaki, Suguru Tamaki
2019 J jnl
Bounded depth circuits with weighted symmetric gates: Satisfiability, lower bounds and compression.
J. Comput. Syst. Sci.
Takayuki Sakai, Kazuhisa Seto, Suguru Tamaki, Junichi Teruyama
2019 J jnl
Depth-scaling fine-grained quantum supremacy based on SETH and qubit-scaling fine-grained quantum supremacy based on Orthogonal Vectors and 3-SUM.
CoRR
Tomoyuki Morimae, Suguru Tamaki
2019 J jnl
Fine-grained quantum computational supremacy.
CoRR
Tomoyuki Morimae, Suguru Tamaki
2019 J jnl
Fine-grained quantum computational supremacy.
Quantum Inf. Comput.
Tomoyuki Morimae, Suguru Tamaki
2019 J jnl
On Computing a Center Persistence Diagram.
CoRR
Yuya Higashikawa, Naoki Katoh, Guohui Lin, Eiji Miyano, Suguru Tamaki, Junichi Teruyama, Binhai Zhu
2019 J jnl
Quantum Query Complexity of Unitary Operator Discrimination.
IEICE Trans. Inf. Syst.
Akinori Kawachi, Kenichi Kawano, Francois Le Gall, Suguru Tamaki
2018 J jnl
Approximation Guarantees for the Minimum Linear Arrangement Problem by Higher Eigenvalues.
ACM Trans. Algorithms
Suguru Tamaki, Yuichi Yoshida
2018 J jnl
Gate elimination: Circuit size lower bounds and #SAT upper bounds.
Theor. Comput. Sci.
Alexander Golovnev, Alexander S. Kulikov, Alexander V. Smal, Suguru Tamaki
2017 A* conf
Beating Brute Force for Systems of Polynomial Equations over Finite Fields.
SODA
Daniel Lokshtanov, Ramamohan Paturi, Suguru Tamaki, R. Ryan Williams, Huacheng Yu
2017 J jnl
Improved exact algorithms for mildly sparse instances of Max SAT.
Theor. Comput. Sci.
Takayuki Sakai, Kazuhisa Seto, Suguru Tamaki, Junichi Teruyama
2017 J jnl
Local Restrictions from the Furst-Saxe-Sipser Paper.
Theory Comput. Syst.
Suguru Tamaki, Osamu Watanabe
2017 Misc conf
Quantum Query Complexity of Unitary Operator Discrimination.
COCOON
Akinori Kawachi, Kenichi Kawano, François Le Gall, Suguru Tamaki
2016 J jnl
A Satisfiability Algorithm for Depth Two Circuits with a Sub-Quadratic Number of Symmetric and Threshold Gates.
Electron. Colloquium Comput. Complex.
Suguru Tamaki
2016 B conf
Bounded Depth Circuits with Weighted Symmetric Gates: Satisfiability, Lower Bounds and Compression.
MFCS
Takayuki Sakai, Kazuhisa Seto, Suguru Tamaki, Junichi Teruyama
2016 J jnl
Bounded Depth Circuits with Weighted Symmetric Gates: Satisfiability, Lower Bounds and Compression.
Electron. Colloquium Comput. Complex.
Takayuki Sakai, Kazuhisa Seto, Suguru Tamaki, Junichi Teruyama
2016 B conf
Circuit Size Lower Bounds and #SAT Upper Bounds Through a General Framework.
MFCS
Alexander Golovnev, Alexander S. Kulikov, Alexander V. Smal, Suguru Tamaki
2016 J jnl
Circuit size lower bounds and #SAT upper bounds through a general framework.
Electron. Colloquium Comput. Complex.
Alexander Golovnev, Alexander S. Kulikov, Alexander Smal, Suguru Tamaki
2015 J jnl
A Satisfiability Algorithm for Depth-2 Circuits with a Symmetric Gate at the Top and AND Gates at the Bottom.
Electron. Colloquium Comput. Complex.
Takayuki Sakai, Kazuhisa Seto, Suguru Tamaki, Junichi Teruyama
2015 J jnl
A query efficient non-adaptive long code test with perfect completeness.
Random Struct. Algorithms
Suguru Tamaki, Yuichi Yoshida
2015 B conf
Improved Exact Algorithms for Mildly Sparse Instances of Max SAT.
IPEC
Takayuki Sakai, Kazuhisa Seto, Suguru Tamaki, Junichi Teruyama
2015 J jnl
Solving Sparse Instances of Max SAT via Width Reduction and Greedy Restriction.
Theory Comput. Syst.
Takayuki Sakai, Kazuhisa Seto, Suguru Tamaki
2014 — conf
Robust Approximation of Temporal CSP.
APPROX-RANDOM
Suguru Tamaki, Yuichi Yoshida
2014 J jnl
Robust Approximation of Temporal CSP.
Electron. Colloquium Comput. Complex.
Suguru Tamaki, Yuichi Yoshida
2014 A conf
Solving Sparse Instances of Max SAT via Width Reduction and Greedy Restriction.
SAT
Takayuki Sakai, Kazuhisa Seto, Suguru Tamaki
2013 J jnl
A satisfiability algorithm and average-case hardness for formulas over the full binary basis.
Comput. Complex.
Kazuhisa Seto, Suguru Tamaki
2013 J jnl
Derandomizing the HSSW Algorithm for 3-SAT.
Algorithmica
Kazuhisa Makino, Suguru Tamaki, Masaki Yamamoto
2012 A conf
A Satisfiability Algorithm and Average-Case Hardness for Formulas over the Full Binary Basis.
CCC
Kazuhisa Seto, Suguru Tamaki
2012 J jnl
A Satisfiability Algorithm and Average-Case Hardness for Formulas over the Full Binary Basis.
Electron. Colloquium Comput. Complex.
Kazuhisa Seto, Suguru Tamaki
2012 — conf
Approximation Guarantees for the Minimum Linear Arrangement Problem by Higher Eigenvalues.
APPROX-RANDOM
Suguru Tamaki, Yuichi Yoshida
2012 A conf
Linear programming, width-1 CSPs, and robust satisfaction.
ITCS
Gábor Kun, Ryan O'Donnell, Suguru Tamaki, Yuichi Yoshida, Yuan Zhou
2011 J jnl
An exact algorithm for the Boolean connectivity problem for k-CNF.
Theor. Comput. Sci.
Kazuhisa Makino, Suguru Tamaki, Masaki Yamamoto
2011 J jnl
Derandomizing HSSW Algorithm for 3-SAT
CoRR
Kazuhisa Makino, Suguru Tamaki, Masaki Yamamoto
2011 Misc conf
Derandomizing HSSW Algorithm for 3-SAT.
COCOON
Kazuhisa Makino, Suguru Tamaki, Masaki Yamamoto
2010 — conf
A Query Efficient Non-adaptive Long Code Test with Perfect Completeness.
APPROX-RANDOM
Suguru Tamaki, Yuichi Yoshida
2010 A conf
An Exact Algorithm for the Boolean Connectivity Problem for
SAT
Kazuhisa Makino, Suguru Tamaki, Masaki Yamamoto
2010 — conf
Improved Randomized Algorithms for 3-SAT.
ISAAC (1)
Kazuo Iwama, Kazuhisa Seto, Tadashi Takai, Suguru Tamaki
2010 J jnl
On the Boolean connectivity problem for Horn relations.
Discret. Appl. Math.
Kazuhisa Makino, Suguru Tamaki, Masaki Yamamoto
2010 J jnl
The Planar Hajós Calculus for Bounded Degree Graphs.
IEICE Trans. Fundam. Electron. Commun. Comput. Sci.
Kazuo Iwama, Kazuhisa Seto, Suguru Tamaki
2010 J jnl
The complexity of the Hajós calculus for planar graphs.
Theor. Comput. Sci.
Kazuo Iwama, Kazuhisa Seto, Suguru Tamaki
2009 J jnl
A Query Efficient Non-Adaptive Long Code Test with Perfect Completeness.
Electron. Colloquium Comput. Complex.
Suguru Tamaki, Yuichi Yoshida
2008 J jnl
New Graph Calculi for Planar Non-3-Colorable Graphs.
IEICE Trans. Fundam. Electron. Commun. Comput. Sci.
Youichi Hanatani, Takashi Horiyama, Kazuo Iwama, Suguru Tamaki
2008 J jnl
The Complexity of the Hajos Calculus for Planar Graphs.
Electron. Colloquium Comput. Complex.
Kazuo Iwama, Suguru Tamaki
2007 J jnl
A Dichotomy Theorem within Schaefer for the Boolean Connectivity Problem.
Electron. Colloquium Comput. Complex.
Kazuhisa Makino, Suguru Tamaki, Masaki Yamamoto
2007 J jnl
Exploiting partial knowledge of satisfying assignments.
Discret. Appl. Math.
Kazuo Iwama, Suguru Tamaki
2007 A conf
On the Boolean Connectivity Problem for Horn Relations.
SAT
Kazuhisa Makino, Suguru Tamaki, Masaki Yamamoto
2004 A* conf
Improved upper bounds for 3-SAT.
SODA
Kazuo Iwama, Suguru Tamaki
2003 J jnl
Improved Upper Bounds for 3-SAT
Electron. Colloquium Comput. Complex.
Kazuo Iwama, Suguru Tamaki
2001 — conf
Exploiting Partial Knowledge of Satisfying Assignments.
WAE
Kazuo Iwama, Suguru Tamaki