288 citations
- University of TsukubaJP49 papers
- Fermi National Accelerator LaboratoryUS44 papers
- University of New MexicoUS44 papers
- Tufts UniversityUS43 papers
- University of LiverpoolGB42 papers
- Waseda UniversityJP42 papers
- Massachusetts Institute of TechnologyUS41 papers
- Okayama UniversityJP41 papers
- University of California, DavisUS41 papers
- University of OxfordGB41 papers
- Yale UniversityUS41 papers
- Academia SinicaTW40 papers
8 papers · 1 filter
A Schematic Definition of Quantum Polynomial Time Computability
Tomoyuki Yamakami
In the past four decades, the notion of quantum polynomial-time computability has been mathematically modeled by quantum Turing machines as well as quantum circuits. This paper see…
The 2CNF Boolean Formula Satisfiability Problem and the Linear Space Hypothesis
Tomoyuki Yamakami
We aim at investigating the solvability/insolvability of nondeterministic logarithmic-space (NL) decision, search, and optimization problems parameterized by natural size parameter…
Counting list matrix partitions of graphs
Andreas Göbel, Leslie Ann Goldberg, Colin McQuillan +2
Given a symmetric D*D matrix M over {0,1,*}, a list M-partition of a graph G is a partition of G's vertices into D parts associated with the rows of M. The part of each vertex is c…
Constant Unary Constraints and Symmetric Real-Weighted Counting Constraint Satisfaction Problems
Tomoyuki Yamakami
A unary constraint (on the Boolean domain) is a function from {0,1} to the set of real numbers. A free use of auxiliary unary constraints given besides input instances has proven t…
Approximation Complexity of Complex-Weighted Degree-Two Counting Constraint Satisfaction Problems
Tomoyuki Yamakami
Constraint satisfaction problems have been studied in numerous fields with practical and theoretical interests. In recent years, major breakthroughs have been made in a study of co…
Optimization, Randomized Approximability, and Boolean Constraint Satisfaction Problems
Tomoyuki Yamakami
We give a unified treatment to optimization problems that can be expressed in the form of nonnegative-real-weighted Boolean constraint satisfaction problems. Creignou, Khanna, Suda…