Stop the war!Остановите войну!
for scientists:
default search action
Google
Google Scholar
Semantic Scholar
Internet Archive Scholar
CiteSeerX
ORCIDTomoyuki Yamakami
Person information
Refine list
refinements active!
zoomed in on ?? of ?? records
view refined list in
export refined list as
showing all ?? records
2020 – today
- 2023
[j36]Tomoyuki Yamakami:
Between SC and LOGDCFL: families of languages accepted by logarithmic-space deterministic auxiliary depth-k storage automata. Int. J. Comput. Math. Comput. Syst. Theory 8(1): 1-31 (2023)- [j35]Tomoyuki Yamakami:
The 2CNF Boolean formula satisfiability problem and the linear space hypothesis. J. Comput. Syst. Sci. 136: 88-112 (2023) - 2022
- [j34]Tomoyuki Yamakami:
How does adiabatic quantum computation fit into quantum automata theory? Inf. Comput. 284: 104694 (2022) - [j33]Tomoyuki Yamakami:
Nonuniform families of polynomial-size quantum finite automata and quantum logarithmic-space computation with polynomial-size advice. Inf. Comput. 286: 104783 (2022) - [c63]Tomoyuki Yamakami:
Nondeterministic Auxiliary Depth-Bounded Storage Automata and Semi-Unbounded Fan-In Cascading Circuits - (Extended Abstract). COCOON 2022: 61-69 - [c62]Tomoyuki Yamakami:
Kolmogorov Complexity Descriptions of the Exquisite Behaviors of Advised Deterministic Pushdown Automata. DLT 2022: 312-324 - [c61]Tomoyuki Yamakami:
Parameterized-NL Completeness of Combinatorial Problems by Short Logarithmic-Space Reductions and Immediate Consequences of the Linear Space Hypothesis. FTC (1) 2022: 776-795 - [c60]Tomoyuki Yamakami:
Formal Grammars for Turn-Bounded Deterministic Context-Free Languages. ICTAC 2022: 425-441 - [c59]Tomoyuki Yamakami:
Fine Grained Space Complexity and the Linear Space Hypothesis (Preliminary Report). ICS 2022: 180-191 - [c58]Tomoyuki Yamakami:
Unambiguity and Fewness for Nonuniform Families of Polynomial-Size Nondeterministic Finite Automata. RP 2022: 77-92 - [c57]Tomoyuki Yamakami:
Expressing Power of Elementary Quantum Recursion Schemes for Quantum Logarithmic-Time Computability. WoLLIC 2022: 88-104 - [i55]Tomoyuki Yamakami:
Between SC and LOGDCFL: Families of Languages Accepted by Logarithmic-Space Deterministic Auxiliary Depth-k Storage Automata. CoRR abs/2203.10193 (2022) - [i54]Tomoyuki Yamakami:
Parameterized-NL Completeness of Combinatorial Problems by Short Logarithmic-Space Reductions and Immediate Consequences of the Linear Space Hypothesis. CoRR abs/2206.10389 (2022) - 2021
- [c56]Tomoyuki Yamakami:
Fuzzy Kolmogorov Complexity Based on Fuzzy Decompression Algorithms and Its Application to Fuzzy Data Mining - (Preliminary Report). ADMA 2021: 421-436 - [c55]Tomoyuki Yamakami:
Between SC and LOGDCFL: Families of Languages Accepted by Polynomial-Time Logarithmic-Space Deterministic Auxiliary Depth-k Storage Automata. COCOON 2021: 164-175 - [c54]Tomoyuki Yamakami, Eitatsu Mikami:
Synchronizing Words for Real-Time Deterministic Pushdown Automata - Extended Abstract. ICMC 2021: 551-562 - [c53]Tomoyuki Yamakami:
Nondeterministically Selecting Positive Instances of Context-Free Languages. ICTCS 2021: 249-265 - [c52]Tomoyuki Yamakami:
Quantum Logical Depth and Shallowness of Streaming Data by One-Way Quantum Finite-State Transducers (Preliminary Report). UCNC 2021: 177-193 - [i53]Tomoyuki Yamakami:
Parameterizations of Logarithmic-Space Reductions, Stack-State Complexity of Nonuniform Families of Pushdown Automata, and a Road to the LOGCFL⊆LOGDCFL/poly Question. CoRR abs/2108.12779 (2021) - [i52]Tomoyuki Yamakami:
The No Endmarker Theorem for One-Way Probabilistic Pushdown Automata. CoRR abs/2111.02688 (2021) - [i51]Tomoyuki Yamakami:
Behavioral Strengths and Weaknesses of Various Models of Limited Automata. CoRR abs/2111.05000 (2021) - [i50]Tomoyuki Yamakami:
Intersection and Union Hierarchies of Deterministic Context-Free Languages and Pumping Lemmas. CoRR abs/2112.09383 (2021) - 2020
- [j32]Tomoyuki Yamakami:
One-Way Topological Automata and the Tantalizing Effects of Their Topological Features. J. Autom. Lang. Comb. 25(2-3): 235-273 (2020) - [j31]Tomoyuki Yamakami:
A Schematic Definition of quantum Polynomial Time Computability. J. Symb. Log. 85(4): 1546-1587 (2020) - [c51]Tomoyuki Yamakami:
Intersection and Union Hierarchies of Deterministic Context-Free Languages and Pumping Lemmas. LATA 2020: 341-353 - [c50]Henning Fernau
, Petra Wolf, Tomoyuki Yamakami:
Synchronizing Deterministic Push-Down Automata Can Be Really Hard. MFCS 2020: 33:1-33:15 - [i49]Tomoyuki Yamakami:
How Does Adiabatic Quantum Computation Fit into Quantum Automata Theory? CoRR abs/2001.05247 (2020) - [i48]Henning Fernau, Petra Wolf, Tomoyuki Yamakami:
Synchronizing Deterministic Push-Down Automata Can Be Really Hard. CoRR abs/2005.01381 (2020)
2010 – 2019
- 2019
- [j30]Tomoyuki Yamakami:
State complexity characterizations of parameterized degree-bounded graph connectivity, sub-linear space computation, and the linear space hypothesis. Theor. Comput. Sci. 798: 2-22 (2019) - [c49]Tomoyuki Yamakami:
How Does Adiabatic Quantum Computation Fit into Quantum Automata Theory? DCFS 2019: 285-297 - [c48]Tomoyuki Yamakami:
Nonuniform Families of Polynomial-Size Quantum Finite Automata and Quantum Logarithmic-Space Computation with Polynomial-Size Advice. LATA 2019: 134-145 - [c47]Tomoyuki Yamakami:
Behavioral Strengths and Weaknesses of Various Models of Limited Automata. SOFSEM 2019: 519-530 - [c46]Tomoyuki Yamakami:
Supportive Oracles for Parameterized Polynomial-Time Sub-Linear-Space Computations in Relation to L, NL, and P. TAMC 2019: 659-673 - [c45]Tomoyuki Yamakami:
Relativizations of Nonuniform Quantum Finite Automata Families. UCNC 2019: 257-271 - [i47]Tomoyuki Yamakami:
Supportive Oracles for Parameterized Polynomial-Time Sub-Linear-Space Computations in Relation to L, NL, and P. CoRR abs/1901.05854 (2019) - [i46]Tomoyuki Yamakami:
One-Way Topological Automata and the Tantalizing Effects of Their Topological Features. CoRR abs/1903.07477 (2019) - [i45]Tomoyuki Yamakami:
Nonuniform Families of Polynomial-Size Quantum Finite Automata and Quantum Logarithmic-Space Computation with Polynomial-Size Advice. CoRR abs/1907.02916 (2019) - 2018
- [c44]Tomoyuki Yamakami:
State Complexity Characterizations of Parameterized Degree-Bounded Graph Connectivity, Sub-Linear Space Computation, and the Linear Space Hypothesis. DCFS 2018: 237-249 - [c43]Tomoyuki Yamakami:
One-way topological automata and the tantalizing effects of their topological features. NCMA 2018: 197-214 - [i44]Tomoyuki Yamakami:
A Schematic Definition of Quantum Polynomial Time Computability. CoRR abs/1802.02336 (2018) - [i43]Tomoyuki Yamakami:
State Complexity Characterizations of Parameterized Degree-Bounded Graph Connectivity, Sub-Linear Space Computation, and the Linear Space Hypothesis. CoRR abs/1811.06336 (2018) - 2017
- [c42]Tomoyuki Yamakami:
One-Way Bounded-Error Probabilistic Pushdown Automata and Kolmogorov Complexity - (Preliminary Report). DLT 2017: 353-364 - [c41]Tomoyuki Yamakami:
The 2CNF Boolean Formula Satisfiability Problem and the Linear Space Hypothesis. MFCS 2017: 62:1-62:14 - [c40]Tomoyuki Yamakami:
A recursive definition of quantum polynomial time computability (extended abstract). NCMA 2017: 243-258 - [c39]Tomoyuki Yamakami:
Parameterized Graph Connectivity and Polynomial-Time Sub-Linear-Space Short Reductions - (Preliminary Report). RP 2017: 176-191 - [i42]Tomoyuki Yamakami:
The 2CNF Boolean Formula Satisfiability Problem and the Linear Space Hypothesis. CoRR abs/1709.10453 (2017) - 2016
- [j29]Tomoyuki Yamakami:
Quantum List Decoding of Classical Block Codes of Polynomially Small Rate from Quantumly Corrupted Codewords. Balt. J. Mod. Comput. 4(4) (2016) - [j28]Tomoyuki Yamakami:
Pseudorandom generators against advised context-free languages. Theor. Comput. Sci. 613: 1-27 (2016) - [i41]Tomoyuki Yamakami:
Uniform-Circuit and Logarithmic-Space Approximations of Refined Combinatorial Optimization Problems. CoRR abs/1601.01118 (2016) - [i40]Tomoyuki Yamakami:
Complexity Bounds of Constant-Space Quantum Computation. CoRR abs/1606.08764 (2016) - [i39]Tomoyuki Yamakami:
Not All Multi-Valued Partial CFL Functions Are Refined by Single-Valued Functions. CoRR abs/1610.07175 (2016) - 2015
- [j27]Andreas Göbel, Leslie Ann Goldberg, Colin McQuillan, David Richerby, Tomoyuki Yamakami:
Counting List Matrix Partitions of Graphs. SIAM J. Comput. 44(4): 1089-1118 (2015) - [j26]Harumichi Nishimura, Tomoyuki Yamakami:
Interactive proofs with quantum finite automata. Theor. Comput. Sci. 568: 1-18 (2015) - [c38]Marcos Villagra, Tomoyuki Yamakami:
Quantum State Complexity of Formal Languages. DCFS 2015: 280-291 - [c37]Tomoyuki Yamakami:
Complexity Bounds of Constant-Space Quantum Computation - (Extended Abstract). DLT 2015: 426-438 - [c36]Tomoyuki Yamakami:
Straight Construction of Non-Interactive Quantum Bit Commitment Schemes from Indistinguishable Quantum State Ensembles. TPNC 2015: 121-133 - [i38]Tomoyuki Yamakami:
Structural Complexity of Multi-Valued Partial Functions Computed by Nondeterministic Pushdown Automata. CoRR abs/1508.05814 (2015) - [i37]Tomoyuki Yamakami:
The World of Combinatorial Fuzzy Problems and the Efficiency of Fuzzy Approximation Algorithms. CoRR abs/1509.03057 (2015) - 2014
- [j25]Tomoyuki Yamakami:
One-way reversible and quantum finite automata with advice. Inf. Comput. 239: 122-148 (2014) - [j24]Tomoyuki Yamakami:
Constant-space quantum interactive proofs against multiple provers. Inf. Process. Lett. 114(11): 611-619 (2014) - [j23]Tomoyuki Yamakami:
Constant Unary Constraints and Symmetric Real-Weighted Counting Constraint Satisfaction Problems. Theory Comput. Syst. 55(1): 170-201 (2014) - [c35]Andreas Göbel, Leslie Ann Goldberg, Colin McQuillan, David Richerby, Tomoyuki Yamakami:
Counting List Matrix Partitions of Graphs. CCC 2014: 56-65 - [c34]Tomoyuki Yamakami:
Structural complexity of multi-valued partial functions computed by nondeterministic pushdown automata. ICTCS 2014: 225-236 - [c33]Tomoyuki Yamakami:
Not All Multi-Valued Partial CFL Functions Are Refined by Single-Valued Functions (Extended Abstract). IFIP TCS 2014: 136-150 - [c32]Tomoyuki Yamakami:
The world of combinatorial fuzzy problems and the efficiency of fuzzy approximation algorithms. SCIS&ISIS 2014: 29-35 - [c31]Tomoyuki Yamakami:
Oracle Pushdown Automata, Nondeterministic Reducibilities, and the Hierarchy over the Family of Context-Free Languages. SOFSEM 2014: 514-525 - [c30]Marcos Villagra, Tomoyuki Yamakami:
Quantum and Reversible Verification of Proofs Using Constant Memory Space. TPNC 2014: 144-156 - [i36]Harumichi Nishimura, Tomoyuki Yamakami:
Interactive Proofs with Quantum Finite Automata. CoRR abs/1401.2929 (2014) - 2013
- [j22]Tomoyuki Yamakami, Yuichi Kato:
The dissecting power of regular languages. Inf. Process. Lett. 113(4): 116-122 (2013) - [c29]Tomoyuki Yamakami:
Uniform-Circuit and Logarithmic-Space Approximations of Refined Combinatorial Optimization Problems. COCOA 2013: 318-329 - [i35]Tomoyuki Yamakami:
Constant Unary Constraints and Symmetric Real-Weighted Counting Constraint Satisfaction Problems. CoRR abs/1303.1347 (2013) - [i34]Tomoyuki Yamakami:
Oracle Pushdown Automata, Nondeterministic Reducibilities, and the Hierarchy over the Family of Context-Free Languages. CoRR abs/1303.1717 (2013) - [i33]Andreas Göbel, Leslie Ann Goldberg, Colin McQuillan, David Richerby, Tomoyuki Yamakami:
Counting list matrix partitions of graphs. CoRR abs/1306.5176 (2013) - [i32]Tomoyuki Yamakami:
Constant-Space Quantum Interactive Proofs Against Multiple Provers. CoRR abs/1309.0429 (2013) - [i31]Tomoyuki Yamakami:
A Non-Interactive Quantum Bit Commitment Scheme that Exploits the Computational Hardness of Quantum State Distinction. CoRR abs/1309.0436 (2013) - 2012
- [j21]Tomoyuki Yamakami:
Approximate counting for complex-weighted Boolean constraint satisfaction problems. Inf. Comput. 219: 17-38 (2012) - [j20]Akinori Kawachi, Takeshi Koshiba, Harumichi Nishimura, Tomoyuki Yamakami:
Computational Indistinguishability Between Quantum States and Its Cryptographic Application. J. Cryptol. 25(3): 528-555 (2012) - [j19]Tomoyuki Yamakami:
A dichotomy theorem for the approximate counting of complex-weighted bounded-degree Boolean CSPs. Theor. Comput. Sci. 447: 120-135 (2012) - [j18]Tomoyuki Yamakami:
Approximation complexity of complex-weighted degree-two counting constraint satisfaction problems. Theor. Comput. Sci. 461: 86-105 (2012) - [c28]Tomoyuki Yamakami:
Constant Unary Constraints and Symmetric Real-Weighted Counting CSPs. ISAAC 2012: 237-246 - [c27]Tomoyuki Yamakami:
One-Way Reversible and Quantum Finite Automata with Advice. LATA 2012: 526-537 - [i30]Tomoyuki Yamakami, Yuichi Kato:
The Dissecting Power of Regular Languages. CoRR abs/1202.4883 (2012) - [i29]Tomoyuki Yamakami:
One-Way Reversible and Quantum Finite Automata with Advice. CoRR abs/1208.6092 (2012) - 2011
- [j17]Tomoyuki Yamakami:
Immunity and pseudorandomness of context-free languages. Theor. Comput. Sci. 412(45): 6432-6450 (2011) - [c26]Tomoyuki Yamakami:
Approximation Complexity of Complex-Weighted Degree-Two Counting Constraint Satisfaction Problems. COCOON 2011: 122-133 - [c25]Tomoyuki Yamakami:
Optimization, Randomized Approximability, and Boolean Constraint Satisfaction Problems. ISAAC 2011: 454-463 - [i28]Tomoyuki Yamakami:
Optimization, Randomized Approximability, and Boolean Constraint Satisfaction Problems. CoRR abs/1109.3651 (2011) - [i27]Tomoyuki Yamakami:
Approximation Complexity of Complex-Weighted Degree-Two Counting Constraint Satisfaction Problems. CoRR abs/1109.5789 (2011) - 2010
- [j16]Tomoyuki Yamakami:
The Roles of Advice to One-Tape Linear-Time Turing Machines and Finite Automata. Int. J. Found. Comput. Sci. 21(6): 941-962 (2010) - [j15]Akinori Kawachi, Tomoyuki Yamakami:
Quantum Hardcore Functions by Complexity-Theoretical Quantum List Decoding. SIAM J. Comput. 39(7): 2941-2969 (2010) - [j14]Kohtaro Tadaki, Tomoyuki Yamakami, Jack C. H. Lin:
Theory of one-tape linear-time Turing machines. Theor. Comput. Sci. 411(1): 22-43 (2010) - [c24]Tomoyuki Yamakami:
A Trichotomy Theorem for the Approximate Counting of Complex-Weighted Bounded-Degree Boolean CSPs. COCOA (1) 2010: 285-299 - [c23]Tomoyuki Yamakami:
Approximate Counting for Complex-Weighted Boolean Constraint Satisfaction Problems. WAOA 2010: 261-272 - [i26]Tomoyuki Yamakami:
Approximate Counting for Complex-Weighted Boolean Constraint Satisfaction Problems. CoRR abs/1007.0391 (2010) - [i25]Tomoyuki Yamakami:
The Roles of Advice to One-Tape Linear-Time Turing Machines and Finite Automata. CoRR abs/1007.3021 (2010) - [i24]Tomoyuki Yamakami:
A Trichotomy Theorem for the Approximate Counting of Complex-Weighted Bounded-Degree Boolean CSPs. CoRR abs/1008.2688 (2010)
2000 – 2009
- 2009
- [j13]Hirotada Kobayashi, Keiji Matsumoto, Tomoyuki Yamakami:
Quantum Merlin-Arthur Proof Systems: Are Multiple Merlins More Helpful to Arthur? Chic. J. Theor. Comput. Sci. 2009 (2009) - [j12]Harumichi Nishimura, Tomoyuki Yamakami:
An application of quantum finite automata to interactive proof systems. J. Comput. Syst. Sci. 75(4): 255-269 (2009) - [c22]Tomoyuki Yamakami:
The Roles of Advice to One-Tape Linear-Time Turing Machines and Finite Automata (Extended Abstract). ISAAC 2009: 933-942 - [i23]Tomoyuki Yamakami:
Immunity and Pseudorandomness of Context-Free Languages. CoRR abs/0902.0261 (2009) - [i22]Tomoyuki Yamakami:
Pseudorandom Generators against CFL/n. CoRR abs/0902.2774 (2009) - 2008
- [i21]Tomoyuki Yamakami:
Swapping Lemmas for Regular and Context-Free Languages with Advice. CoRR abs/0808.4122 (2008) - 2007
- [c21]Tomoyuki Yamakami:
Quantum List Decoding from Quantumly Corrupted Codewords for Classical Block Codes of Polynomially Small Rate. CATS 2007: 153-162 - 2006
- [c20]Akinori Kawachi, Tomoyuki Yamakami:
Quantum Hardcore Functions by Complexity-Theoretical Quantum List Decoding. ICALP (2) 2006: 216-227 - [i20]Akinori Kawachi, Tomoyuki Yamakami:
Quantum Hardcore Functions by Complexity-Theoretical Quantum List Decoding. CoRR abs/quant-ph/0602088 (2006) - [i19]Tomoyuki Yamakami:
Quantum List Decoding of Classical Block Codes of Polynomially Small Rate from Quantumly Corrupted Codewords. CoRR abs/quant-ph/0610200 (2006) - [i18]Akinori Kawachi, Tomoyuki Yamakami:
Quantum Hardcore Functions by Complexity-Theoretical Quantum List Decoding. Electron. Colloquium Comput. Complex. TR06 (2006) - [i17]Akinori Kawachi, Takeshi Koshiba, Harumichi Nishimura, Tomoyuki Yamakami:
Computational Indistinguishability between Quantum States and Its Cryptographic Application. IACR Cryptol. ePrint Arch. 2006: 148 (2006) - 2005
- [j11]Tomoyuki Yamakami, Toshio Suzuki:
Resource bounded immunity and simplicity. Theor. Comput. Sci. 347(1-2): 90-129 (2005) - [c19]Akinori Kawachi, Takeshi Koshiba, Harumichi Nishimura, Tomoyuki Yamakami:
Computational Indistinguishability Between Quantum States and Its Cryptographic Application. EUROCRYPT 2005: 268-284 - [c18]Tomoyuki Yamakami:
Collapsing Recursive Oracles for Relativized Polynomial Hierarchies. FCT 2005: 149-160 - [i16]Harumichi Nishimura, Tomoyuki Yamakami:
Quantum Minimal One Way Information: Relative Hardness and Quantum Advantage of Combinatorial Tasks. CoRR abs/quant-ph/0507270 (2005) - 2004
- [j10]Harumichi Nishimura, Tomoyuki Yamakami:
Polynomial time quantum computation with advice. Inf. Process. Lett. 90(4): 195-204 (2004) - [c17]Toshio Suzuki, Tomoyuki Yamakami:
Resource Bounded Immunity and Simplicity. IFIP TCS 2004: 81-96 - [c16]Harumichi Nishimura, Tomoyuki Yamakami:
An Algorithmic Argument for Nonadaptive Query Complexity Lower Bounds on Advised Quantum Computation (Extended Abstract). MFCS 2004: 827-838 - [c15]Kohtaro Tadaki, Tomoyuki Yamakami, Jack C. H. Lin:
Theory of One Tape Linear Time Turing Machines. SOFSEM 2004: 335-348 - [c14]Harumichi Nishimura, Tomoyuki Yamakami:
An Application of Quantum Finite Automata to Interactive Proof Systems. CIAA 2004: 225-236 - [i15]Tomoyuki Yamakami, Toshio Suzuki:
Resource Bounded Immunity and Simplicity. CoRR cs.CC/0407015 (2004) - [i14]Harumichi Nishimura, Tomoyuki Yamakami:
An Application of Quantum Finite Automata to Interactive Proof Systems. CoRR quant-ph/0410040 (2004) - [i13]Tomoyuki Yamakami, Toshio Suzuki:
Resource Bounded Immunity and Simplicity. Electron. Colloquium Comput. Complex. TR04 (2004) - [i12]Tomoyuki Yamakami, Harumichi Nishimura:
An Application of Quantum Finite Automata to Interactive Proof Systems. Electron. Colloquium Comput. Complex. TR04 (2004) - 2003
- [j9]Tomoyuki Yamakami:
Analysis Of Quantum Functions. Int. J. Found. Comput. Sci. 14(5): 815-852 (2003) - [c13]Tomoyuki Yamakami:
Nearly Bounded Error Probabilistic Sets. CIAC 2003: 213-226 - [c12]Tomoyuki Yamakami:
Computational Complexity Measures of Multipartite Quantum Entanglement. ISAAC 2003: 117-128 - [c11]Hirotada Kobayashi, Keiji Matsumoto, Tomoyuki Yamakami:
Quantum Merlin-Arthur Proof Systems: Are Multiple Merlins More Helpful to Arthur? ISAAC 2003: 189-198 - [i11]Kohtaro Tadaki, Tomoyuki Yamakami, Jack C. H. Lin:
Theory of One Tape Linear Time Turing Machines. CoRR <