Suguru Tamaki

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

2020

Additive-error fine-grained quantum supremacy.

[BibT_eX]

[DOI]

Tomoyuki Morimae

Quantum, 2020

2019

Fine-grained quantum computational supremacy.

[BibT_eX]

[DOI]

Tomoyuki Morimae

Quantum Inf. Comput., 2019

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

[BibT_eX]

[DOI]

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.

[BibT_eX]

[DOI]

Tomoyuki Morimae

CoRR, 2019

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

[BibT_eX]

[DOI]

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

2018

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

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2018

2017

Local Restrictions from the Furst-Saxe-Sipser Paper.

[BibT_eX]

[DOI]

Osamu Watanabe

Theory Comput. Syst., 2017

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

[BibT_eX]

[DOI]

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

Quantum Query Complexity of Unitary Operator Discrimination.

[BibT_eX]

[DOI]

Proceedings of the Computing and Combinatorics - 23rd International Conference, 2017

2016

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

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2016

Bounded Depth Circuits with Weighted Symmetric Gates: Satisfiability, Lower Bounds and Compression.

[BibT_eX]

[DOI]

Proceedings of the 41st International Symposium on Mathematical Foundations of Computer Science, 2016

Circuit Size Lower Bounds and #SAT Upper Bounds Through a General Framework.

[BibT_eX]

[DOI]

Proceedings of the 41st International Symposium on Mathematical Foundations of Computer Science, 2016

2015

A Satisfiability Algorithm for Depth-2 Circuits with a Symmetric Gate at the Top and AND Gates at the Bottom.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2015

Improved Exact Algorithms for Mildly Sparse Instances of Max SAT.

[BibT_eX]

[DOI]

Proceedings of the 10th International Symposium on Parameterized and Exact Computation, 2015

2014

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

[BibT_eX]

[DOI]

Takayuki Sakai

Proceedings of the Theory and Applications of Satisfiability Testing - SAT 2014, 2014

Robust Approximation of Temporal CSP.

[BibT_eX]

[DOI]

Yuichi Yoshida

Proceedings of the Approximation, 2014

2012

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

[BibT_eX]

[DOI]

Proceedings of the Innovations in Theoretical Computer Science 2012, 2012

A Satisfiability Algorithm and Average-Case Hardness for Formulas over the Full Binary Basis.

[BibT_eX]

[DOI]

Proceedings of the 27th Conference on Computational Complexity, 2012

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

[BibT_eX]

[DOI]

Yuichi Yoshida

Proceedings of the Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, 2012

2011

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

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2011

Derandomizing HSSW Algorithm for 3-SAT.

[BibT_eX]

[DOI]

Proceedings of the Computing and Combinatorics - 17th Annual International Conference, 2011

2010

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

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2010

The Planar Hajós Calculus for Bounded Degree Graphs.

[BibT_eX]

[DOI]

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

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

[BibT_eX]

[DOI]

Proceedings of the Theory and Applications of Satisfiability Testing, 2010

Improved Randomized Algorithms for 3-SAT.

[BibT_eX]

[DOI]

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

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

[BibT_eX]

[DOI]

Yuichi Yoshida

Proceedings of the Approximation, 2010

2008

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

[BibT_eX]

[DOI]

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

The Complexity of the Hajos Calculus for Planar Graphs.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2008

2007

A Dichotomy Theorem within Schaefer for the Boolean Connectivity Problem.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2007

On the Boolean Connectivity Problem for Horn Relations.

[BibT_eX]

[DOI]

Proceedings of the Theory and Applications of Satisfiability Testing, 2007

2004

Improved upper bounds for 3-SAT.

[BibT_eX]

[DOI]

Proceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2004

2001

Exploiting Partial Knowledge of Satisfying Assignments.

[BibT_eX]

[DOI]