


Остановите войну!
for scientists:
Tomoyuki 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
- 2022
- [j33]Tomoyuki Yamakami:
How does adiabatic quantum computation fit into quantum automata theory? Inf. Comput. 284: 104694 (2022) - [c57]Tomoyuki Yamakami:
Kolmogorov Complexity Descriptions of the Exquisite Behaviors of Advised Deterministic Pushdown Automata. DLT 2022: 312-324 - [i54]Tomoyuki Yamakami:
Between SC and LOGDCFL: Families of Languages Accepted by Logarithmic-Space Deterministic Auxiliary Depth-k Storage Automata. CoRR abs/2203.10193 (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. Computational Complexity Conference 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. 13(020) (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.(066) (2004) - [i12]Tomoyuki Yamakami, Harumichi Nishimura:
An Application of Quantum Finite Automata to Interactive Proof Systems. Electron. Colloquium Comput. Complex.(110) (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 cs.CC/0310046 (2003) - [i10]Harumichi Nishimura, Tomoyuki Yamakami:
Polynomial time quantum computation with advice. CoRR quant-ph/0305100 (2003) - [i9]Tomoyuki Yamakami:
Computational Complexity Measures of Multipartite Quantum Entanglement. CoRR quant-ph/0308072 (2003) - [i8]Harumichi Nishimura, Tomoyuki Yamakami:
An Algorithmic Argument for Query Complexity Lower Bounds of Advised Quantum Computation. CoRR quant-ph/0312003 (2003) - [i7]Harumichi Nishimura, Tomoyuki Yamakami:
Polynomial time quantum computation with advice. Electron. Colloquium Comput. Complex.(059) (2003) - 2002
- [c10]Jeffrey C. Jackson, Christino Tamon, Tomoyuki Yamakami:
Quantum DNF Learnability Revisited. COCOON 2002: 595-604 - [c9]Tomoyuki Yamakami:
Quantum NP and Quantum Hierarchy. IFIP TCS 2002: 323-336 - [c8]Tomoyuki Yamakami:
Quantum Optimization Problems. UMC 2002: 300-314 - 2001
- [i6]Hirotada Kobayashi, Keiji Matsumoto, Tomoyuki Yamakami:
Quantum Certificate Verification: Single versus Multiple Quantum Certificates. CoRR quant-ph/0110006 (2001) - 2000
- [c7]Christino Tamon, Tomoyuki Yamakami:
Quantum Computation Relative to Oracles. UMC 2000: 273-288
1990 – 1999
- 1999
- [j8]Tomoyuki Yamakami, Andrew Chi-Chih Yao:
NQPC = co-C=P. Inf. Process. Lett. 71(2): 63-69 (1999) - [j7]Tomoyuki Yamakami:
Polynomial Time Samplable Distributions. J. Complex. 15(4): 557-574 (1999) - [c6]Tomoyuki Yamakami:
Analysis of Quantum Functions (Preliminary Version). FSTTCS 1999: 407-419 - [c5]Tomoyuki Yamakami:
A Foundation of Programming a Multi-tape Quantum Turing Machine. MFCS 1999: 430-441 - [i5]