Tomoyuki Yamakami

According to our database1, Tomoyuki Yamakami authored at least 97 papers between 1992 and 2023.

Collaborative distances:

Timeline

Legend:

Book 
In proceedings 
Article 
PhD thesis 
Dataset
Other 

Links

Online presence:

On csauthors.net:

Bibliography

2023
Synchronizing deterministic push-down automata can be really hard.
Inf. Comput., December, 2023

Between SC and LOGDCFL: families of languages accepted by logarithmic-space deterministic auxiliary depth-<i>k</i> storage automata.
Int. J. Comput. Math. Comput. Syst. Theory, January, 2023

The 2CNF Boolean formula satisfiability problem and the linear space hypothesis.
J. Comput. Syst. Sci., 2023

Elementary Quantum Recursion Schemes That Capture Quantum Polylogarithmic Time Computability of Quantum Functions.
CoRR, 2023

When Input Integers are Given in the Unary Numeral Representation.
Proceedings of the 24th Italian Conference on Theoretical Computer Science, 2023

Power of Counting by Nonuniform Families of Polynomial-Size Finite Automata.
Proceedings of the Fundamentals of Computation Theory - 24th International Symposium, 2023

2022
Nonuniform families of polynomial-size quantum finite automata and quantum logarithmic-space computation with polynomial-size advice.
Inf. Comput., 2022

How does adiabatic quantum computation fit into quantum automata theory?
Inf. Comput., 2022

Between SC and LOGDCFL: Families of Languages Accepted by Logarithmic-Space Deterministic Auxiliary Depth-k Storage Automata.
CoRR, 2022

Expressing Power of Elementary Quantum Recursion Schemes for Quantum Logarithmic-Time Computability.
Proceedings of the Logic, Language, Information, and Computation, 2022

Unambiguity and Fewness for Nonuniform Families of Polynomial-Size Nondeterministic Finite Automata.
Proceedings of the Reachability Problems - 16th International Conference, 2022

Fine Grained Space Complexity and the Linear Space Hypothesis (Preliminary Report).
Proceedings of the New Trends in Computer Technologies and Applications, 2022

Formal Grammars for Turn-Bounded Deterministic Context-Free Languages.
Proceedings of the Theoretical Aspects of Computing - ICTAC 2022, 2022

Parameterized-NL Completeness of Combinatorial Problems by Short Logarithmic-Space Reductions and Immediate Consequences of the Linear Space Hypothesis.
Proceedings of the Future Technologies Conference, 2022

Kolmogorov Complexity Descriptions of the Exquisite Behaviors of Advised Deterministic Pushdown Automata.
Proceedings of the Developments in Language Theory - 26th International Conference, 2022

Nondeterministic Auxiliary Depth-Bounded Storage Automata and Semi-Unbounded Fan-In Cascading Circuits - (Extended Abstract).
Proceedings of the Computing and Combinatorics - 28th International Conference, 2022

2021
The No Endmarker Theorem for One-Way Probabilistic Pushdown Automata.
CoRR, 2021

Parameterizations of Logarithmic-Space Reductions, Stack-State Complexity of Nonuniform Families of Pushdown Automata, and a Road to the LOGCFL⊆LOGDCFL/poly Question.
CoRR, 2021

Quantum Logical Depth and Shallowness of Streaming Data by One-Way Quantum Finite-State Transducers (Preliminary Report).
Proceedings of the Unconventional Computation and Natural Computation, 2021

Nondeterministically Selecting Positive Instances of Context-Free Languages.
Proceedings of the 22nd Italian Conference on Theoretical Computer Science, 2021

Synchronizing Words for Real-Time Deterministic Pushdown Automata - Extended Abstract.
Proceedings of the Seventh International Conference on Mathematics and Computing, 2021

Between SC and LOGDCFL: Families of Languages Accepted by Polynomial-Time Logarithmic-Space Deterministic Auxiliary Depth-k Storage Automata.
Proceedings of the Computing and Combinatorics - 27th International Conference, 2021

Fuzzy Kolmogorov Complexity Based on Fuzzy Decompression Algorithms and Its Application to Fuzzy Data Mining - (Preliminary Report).
Proceedings of the Advanced Data Mining and Applications - 17th International Conference, 2021

2020
A Schematic Definition of quantum Polynomial Time Computability.
J. Symb. Log., 2020

One-Way Topological Automata and the Tantalizing Effects of Their Topological Features.
J. Autom. Lang. Comb., 2020

Intersection and Union Hierarchies of Deterministic Context-Free Languages and Pumping Lemmas.
Proceedings of the Language and Automata Theory and Applications, 2020

2019
State complexity characterizations of parameterized degree-bounded graph connectivity, sub-linear space computation, and the linear space hypothesis.
Theor. Comput. Sci., 2019

Relativizations of Nonuniform Quantum Finite Automata Families.
Proceedings of the Unconventional Computation and Natural Computation, 2019

Supportive Oracles for Parameterized Polynomial-Time Sub-Linear-Space Computations in Relation to L, NL, and P.
Proceedings of the Theory and Applications of Models of Computation, 2019

Behavioral Strengths and Weaknesses of Various Models of Limited Automata.
Proceedings of the SOFSEM 2019: Theory and Practice of Computer Science, 2019

2017
Parameterized Graph Connectivity and Polynomial-Time Sub-Linear-Space Short Reductions - (Preliminary Report).
Proceedings of the Reachability Problems - 11th International Workshop, 2017

A recursive definition of quantum polynomial time computability (extended abstract).
Proceedings of the Ninth Workshop on Non-Classical Models of Automata and Applications, 2017

One-Way Bounded-Error Probabilistic Pushdown Automata and Kolmogorov Complexity - (Preliminary Report).
Proceedings of the Developments in Language Theory - 21st International Conference, 2017

2016
Pseudorandom generators against advised context-free languages.
Theor. Comput. Sci., 2016

Not All Multi-Valued Partial CFL Functions Are Refined by Single-Valued Functions.
CoRR, 2016

Complexity Bounds of Constant-Space Quantum Computation.
CoRR, 2016

Quantum List Decoding of Classical Block Codes of Polynomially Small Rate from Quantumly Corrupted Codewords.
Balt. J. Mod. Comput., 2016

2015
Interactive proofs with quantum finite automata.
Theor. Comput. Sci., 2015

Counting List Matrix Partitions of Graphs.
SIAM J. Comput., 2015

Straight Construction of Non-Interactive Quantum Bit Commitment Schemes from Indistinguishable Quantum State Ensembles.
Proceedings of the Theory and Practice of Natural Computing, 2015

Complexity Bounds of Constant-Space Quantum Computation - (Extended Abstract).
Proceedings of the Developments in Language Theory - 19th International Conference, 2015

Quantum State Complexity of Formal Languages.
Proceedings of the Descriptional Complexity of Formal Systems, 2015

2014
Constant Unary Constraints and Symmetric Real-Weighted Counting Constraint Satisfaction Problems.
Theory Comput. Syst., 2014

Constant-space quantum interactive proofs against multiple provers.
Inf. Process. Lett., 2014

One-way reversible and quantum finite automata with advice.
Inf. Comput., 2014

Quantum and Reversible Verification of Proofs Using Constant Memory Space.
Proceedings of the Theory and Practice of Natural Computing, 2014

Oracle Pushdown Automata, Nondeterministic Reducibilities, and the Hierarchy over the Family of Context-Free Languages.
Proceedings of the SOFSEM 2014: Theory and Practice of Computer Science, 2014

The world of combinatorial fuzzy problems and the efficiency of fuzzy approximation algorithms.
Proceedings of the 2014 Joint 7th International Conference on Soft Computing and Intelligent Systems (SCIS) and 15th International Symposium on Advanced Intelligent Systems (ISIS), 2014

Not All Multi-Valued Partial CFL Functions Are Refined by Single-Valued Functions (Extended Abstract).
Proceedings of the Theoretical Computer Science, 2014

Structural complexity of multi-valued partial functions computed by nondeterministic pushdown automata.
Proceedings of the 15th Italian Conference on Theoretical Computer Science, 2014

2013
The dissecting power of regular languages.
Inf. Process. Lett., 2013

A Non-Interactive Quantum Bit Commitment Scheme that Exploits the Computational Hardness of Quantum State Distinction.
CoRR, 2013

Uniform-Circuit and Logarithmic-Space Approximations of Refined Combinatorial Optimization Problems.
Proceedings of the Combinatorial Optimization and Applications, 2013

2012
Approximation complexity of complex-weighted degree-two counting constraint satisfaction problems.
Theor. Comput. Sci., 2012

A dichotomy theorem for the approximate counting of complex-weighted bounded-degree Boolean CSPs.
Theor. Comput. Sci., 2012

Computational Indistinguishability Between Quantum States and Its Cryptographic Application.
J. Cryptol., 2012

Approximate counting for complex-weighted Boolean constraint satisfaction problems.
Inf. Comput., 2012

Constant Unary Constraints and Symmetric Real-Weighted Counting CSPs.
Proceedings of the Algorithms and Computation - 23rd International Symposium, 2012

2011
Immunity and pseudorandomness of context-free languages.
Theor. Comput. Sci., 2011

Optimization, Randomized Approximability, and Boolean Constraint Satisfaction Problems.
Proceedings of the Algorithms and Computation - 22nd International Symposium, 2011

2010
Theory of one-tape linear-time Turing machines.
Theor. Comput. Sci., 2010

The Roles of Advice to One-Tape Linear-Time Turing Machines and Finite Automata.
Int. J. Found. Comput. Sci., 2010

A Trichotomy Theorem for the Approximate Counting of Complex-Weighted Bounded-Degree Boolean CSPs.
Proceedings of the Combinatorial Optimization and Applications, 2010

2009
An application of quantum finite automata to interactive proof systems.
J. Comput. Syst. Sci., 2009

Pseudorandom Generators against CFL/n
CoRR, 2009

Quantum Merlin-Arthur Proof Systems: Are Multiple Merlins More Helpful to Arthur?
Chic. J. Theor. Comput. Sci., 2009

The Roles of Advice to One-Tape Linear-Time Turing Machines and Finite Automata (Extended Abstract).
Proceedings of the Algorithms and Computation, 20th International Symposium, 2009

2008
Swapping Lemmas for Regular and Context-Free Languages with Advice
CoRR, 2008

2007
Quantum List Decoding from Quantumly Corrupted Codewords for Classical Block Codes of Polynomially Small Rate.
Proceedings of the Theory of Computing 2007. Proceedings of the Thirteenth Computing: The Australasian Theory Symposium (CATS2007). January 30, 2007

2006
Quantum Hardcore Functions by Complexity-Theoretical Quantum List Decoding.
Electron. Colloquium Comput. Complex., 2006

2005
Resource bounded immunity and simplicity.
Theor. Comput. Sci., 2005

Quantum Minimal One Way Information: Relative Hardness and Quantum Advantage of Combinatorial Tasks
CoRR, 2005

Collapsing Recursive Oracles for Relativized Polynomial Hierarchies.
Proceedings of the Fundamentals of Computation Theory, 15th International Symposium, 2005

2004
Polynomial time quantum computation with advice.
Inf. Process. Lett., 2004

An Algorithmic Argument for Nonadaptive Query Complexity Lower Bounds on Advised Quantum Computation (Extended Abstract).
Proceedings of the Mathematical Foundations of Computer Science 2004, 2004

2003
Analysis Of Quantum Functions.
Int. J. Found. Comput. Sci., 2003

An Algorithmic Argument for Query Complexity Lower Bounds of Advised Quantum Computation
CoRR, 2003

Computational Complexity Measures of Multipartite Quantum Entanglement.
Proceedings of the Algorithms and Computation, 14th International Symposium, 2003

Nearly Bounded Error Probabilistic Sets.
Proceedings of the Algorithms and Complexity, 5th Italian Conference, 2003

2002
Quantum Optimization Problems.
Proceedings of the Unconventional Models of Computation, Third International Conference, 2002

Quantum NP and Quantum Hierarchy.
Proceedings of the Foundations of Information Technology in the Era of Networking and Mobile Computing, 2002

Quantum DNF Learnability Revisited.
Proceedings of the Computing and Combinatorics, 8th Annual International Conference, 2002

2001
Quantum Certificate Verification: Single versus Multiple Quantum Certificates
CoRR, 2001

2000
Quantum Computation Relative to Oracles.
Proceedings of the Unconventional Models of Computation, 2000

1999
NQP<sub>C</sub> = co-C<sub>=</sub>P.
Inf. Process. Lett., 1999

A Foundation of Programming a Multi-tape Quantum Turing Machine.
Proceedings of the Mathematical Foundations of Computer Science 1999, 1999

Analysis of Quantum Functions (Preliminary Version).
Proceedings of the Foundations of Software Technology and Theoretical Computer Science, 1999

1998
NQP = co-C<sub>=</sub>P
Electron. Colloquium Comput. Complex., 1998

1997
Average case computational complexity theory.
PhD thesis, 1997

A Tight Relationship Between Generic Oracles and Type-2 Complexity Theory.
Inf. Comput., 1997

1996
Structural Average Case Complexity.
J. Comput. Syst. Sci., 1996

Generic Separations.
J. Comput. Syst. Sci., 1996

Polynomial Games and Determinacy.
Ann. Pure Appl. Log., 1996

1995
Feasible Computability and Resource Bounded Topology
Inf. Comput., February, 1995

Polynomial Time Samplable Distributions
Electron. Colloquium Comput. Complex., 1995

Sets Computable in Polynomial Time on Average.
Proceedings of the Computing and Combinatorics, First Annual International Conference, 1995

1992
Structural Properties for Feasibly Computable Classes of Type Two.
Math. Syst. Theory, 1992


  Loading...