Suguru Tamaki

Publication Activity (10 Years)

Years Active: 2001-2024
Publications (10 Years): 23

Top Topics

Query Complexity

Top Venues

Electron. Colloquium Comput. Complex.

Theor. Comput. Sci.

Publications

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