Suguru Tamaki

According to our database, Suguru Tamaki authored at least 35 papers between 2003 and 2024.

Collaborative distances:

• Dijkstra number of three.
• Erdős number of three.

2024

Beating Grover search for low-energy estimation and state preparation.

Harry Buhrman, Sevag Gharibian, Zeph Landau, François Le Gall, Norbert Schuch, Suguru Tamaki

CoRR, 2024

2023

On Computing a Center Persistence Diagram.

Yuya Higashikawa, Naoki Katoh, Guohui Lin, Eiji Miyano, Suguru Tamaki, Junichi Teruyama, Binhai Zhu

Proceedings of the Fundamentals of Computation Theory - 24th International Symposium, 2023

2022

Foreword.

Suguru Tamaki

IEICE Trans. Fundam. Electron. Commun. Comput. Sci., September, 2022

2020

Additive-error fine-grained quantum supremacy.

Tomoyuki Morimae, Suguru Tamaki

Quantum, 2020

2019

Fine-grained quantum computational supremacy.

Tomoyuki Morimae, Suguru Tamaki

Quantum Inf. Comput., 2019

Bounded depth circuits with weighted symmetric gates: Satisfiability, lower bounds and compression.

Takayuki Sakai, Kazuhisa Seto, Suguru Tamaki, Junichi Teruyama

J. Comput. Syst. Sci., 2019

Quantum Query Complexity of Unitary Operator Discrimination.

Akinori Kawachi, Kenichi Kawano, Francois Le Gall, Suguru Tamaki

IEICE Trans. Inf. Syst., 2019

An FPT Algorithm for Max-Cut Parameterized by Crossing Number.

Yasuaki Kobayashi, Yusuke Kobayashi, Shuichi Miyazaki, Suguru Tamaki

CoRR, 2019

Depth-scaling fine-grained quantum supremacy based on SETH and qubit-scaling fine-grained quantum supremacy based on Orthogonal Vectors and 3-SUM.

Tomoyuki Morimae, Suguru Tamaki

CoRR, 2019

An Improved Fixed-Parameter Algorithm for Max-Cut Parameterized by Crossing Number.

Yasuaki Kobayashi, Yusuke Kobayashi, Shuichi Miyazaki, Suguru Tamaki

Proceedings of the Combinatorial Algorithms - 30th International Workshop, 2019

2018

Gate elimination: Circuit size lower bounds and #SAT upper bounds.

Alexander Golovnev, Alexander S. Kulikov, Alexander V. Smal, Suguru Tamaki

Theor. Comput. Sci., 2018

Approximation Guarantees for the Minimum Linear Arrangement Problem by Higher Eigenvalues.

Suguru Tamaki, Yuichi Yoshida

ACM Trans. Algorithms, 2018

2017

Improved exact algorithms for mildly sparse instances of Max SAT.

Takayuki Sakai, Kazuhisa Seto, Suguru Tamaki, Junichi Teruyama

Theor. Comput. Sci., 2017

Local Restrictions from the Furst-Saxe-Sipser Paper.

Suguru Tamaki, Osamu Watanabe

Theory Comput. Syst., 2017

Beating Brute Force for Systems of Polynomial Equations over Finite Fields.

Daniel Lokshtanov, Ramamohan Paturi, Suguru Tamaki, R. Ryan Williams, Huacheng Yu

Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, 2017

2016

A Satisfiability Algorithm for Depth Two Circuits with a Sub-Quadratic Number of Symmetric and Threshold Gates.

Suguru Tamaki

Electron. Colloquium Comput. Complex., 2016

Circuit size lower bounds and #SAT upper bounds through a general framework.

Alexander Golovnev, Alexander S. Kulikov, Alexander Smal, Suguru Tamaki

Electron. Colloquium Comput. Complex., 2016

2015

Solving Sparse Instances of Max SAT via Width Reduction and Greedy Restriction.

Takayuki Sakai, Kazuhisa Seto, Suguru Tamaki

Theory Comput. Syst., 2015

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

Electron. Colloquium Comput. Complex., 2015

2014

Robust Approximation of Temporal CSP.

Suguru Tamaki, Yuichi Yoshida

Electron. Colloquium Comput. Complex., 2014

2013

A satisfiability algorithm and average-case hardness for formulas over the full binary basis.

Kazuhisa Seto, Suguru Tamaki

Comput. Complex., 2013

Derandomizing the HSSW Algorithm for 3-SAT.

Kazuhisa Makino, Suguru Tamaki, Masaki Yamamoto

Algorithmica, 2013

2012

Linear programming, width-1 CSPs, and robust satisfaction.

Gábor Kun, Ryan O'Donnell, Suguru Tamaki, Yuichi Yoshida, Yuan Zhou

Proceedings of the Innovations in Theoretical Computer Science 2012, 2012

2011

An exact algorithm for the Boolean connectivity problem for k-CNF.

Kazuhisa Makino, Suguru Tamaki, Masaki Yamamoto

Theor. Comput. Sci., 2011

2010

The complexity of the Hajós calculus for planar graphs.

Kazuo Iwama, Kazuhisa Seto, Suguru Tamaki

Theor. Comput. Sci., 2010

The Planar Hajós Calculus for Bounded Degree Graphs.

Kazuo Iwama, Kazuhisa Seto, Suguru Tamaki

IEICE Trans. Fundam. Electron. Commun. Comput. Sci., 2010

On the Boolean connectivity problem for Horn relations.

Kazuhisa Makino, Suguru Tamaki, Masaki Yamamoto

Discret. Appl. Math., 2010

An Exact Algorithm for the Boolean Connectivity Problem for <i>k</i>-CNF.

Kazuhisa Makino, Suguru Tamaki, Masaki Yamamoto

Proceedings of the Theory and Applications of Satisfiability Testing, 2010

Improved Randomized Algorithms for 3-SAT.

Kazuo Iwama, Kazuhisa Seto, Tadashi Takai, Suguru Tamaki

Proceedings of the Algorithms and Computation - 21st International Symposium, 2010

2009

A Query Efficient Non-Adaptive Long Code Test with Perfect Completeness.

Suguru Tamaki, Yuichi Yoshida

Electron. Colloquium Comput. Complex., 2009

2008

New Graph Calculi for Planar Non-3-Colorable Graphs.

Youichi Hanatani, Takashi Horiyama, Kazuo Iwama, Suguru Tamaki

IEICE Trans. Fundam. Electron. Commun. Comput. Sci., 2008

The Complexity of the Hajos Calculus for Planar Graphs.

Kazuo Iwama, Suguru Tamaki

Electron. Colloquium Comput. Complex., 2008

2007

A Dichotomy Theorem within Schaefer for the Boolean Connectivity Problem.

Kazuhisa Makino, Suguru Tamaki, Masaki Yamamoto

Electron. Colloquium Comput. Complex., 2007

Exploiting partial knowledge of satisfying assignments.

Kazuo Iwama, Suguru Tamaki

Discret. Appl. Math., 2007

2003

Improved Upper Bounds for 3-SAT

Kazuo Iwama, Suguru Tamaki

Electron. Colloquium Comput. Complex., 2003