YAMAKAMI, Tomoyuki

FacultyInformation Science
Teacher OrganizationInformation Science
Education and
 Research Organization
Faculty of Engineering /Graduate School of Engineering
PositionProfessor
Last Updated: 19/11/26 15:12

Researcher Profile & Settings

Name

    YAMAKAMI, Tomoyuki

Profile & Settings

Affiliation

  •  Information Science Professor

Association Memberships

    European Association for Theoretical Computer Science (EATCS),

Research Activities

Published Papers

  • The 2CNF Boolean formula satisfiability problem and the linear space hypothesis
    Tomoyuki Yamakami
    Proceedings of the 42nd International Symposium on Mathematical Foundations of Computer Science, Leibniz International Proceedings in Informatics 2017 Refereed
  • Parameterized graph connectivity and polynomial-time sub-linear-space short reductions - (preliminary report)
    Tomoyuki Yamakami
    Proceedings of the 11th International Workshop on Reachability Problems, Lecture Notes in Computer Science 10506 176-191 2017 Refereed
  • A recursive definition of quantum polynomial time computability (extended abstract)
    Tomoyuki Yamakami
    Proceedings of the Ninth Workshop on Non-Classical Models of Automata and Applications, Österreichische Computer Gesellschaft 2017 243-258 2017 Refereed
  • One-way bounded-error probabilistic pushdown automata and Kolmogorov complexity - (preliminary report)
    Tomoyuki Yamakami
    Proceedings of the 21st International Conference on Developments in Language Theory, Lecture Notes in Computer Science 10396 353-364 2017 Refereed
  • Quantum list decoding of classical block codes of polynomially small rate from quantumly corrupted codewords
    Tomoyuki Yamakami
    Baltic Journal on Modern Computing 4(4) 753-788 2016 Refereed
  • Pseudorandom generators against advised context-free languages
    Tomoyuki Yamakami
    Theoretical Computer Science 613 1-27 2016 Refereed
  • Straight construction of non-interactive quantum bit commitment schemes from indistinguishable quantum state ensembles
    Tomoyuki Yamakami
    Proceedings of the Fourth International Conference on Theory and Practice of Natural Computing, Lecture Notes in Computer Science 9477 121-133 2015 Refereed
  • Complexity bounds of constant-space quantum computation - (extended abstract)
    Tomoyuki Yamakami
    Proceedings of the 19th International Conference on Developments in Language Theory, Lecture Notes in Computer Science 9168 426-438 2015 Refereed
  • Quantum state complexity of formal languages
    Marcos Villagra, Tomoyuki Yamakami
    Proceedings of the 17th International Workshop on Descriptional Complexity of Formal Systems, Lecture Notes in Computer Science 9118 280-291 2015 Refereed
  • Interactive proofs with quantum finite automata
    Harumichi Nishimura, Tomoyuki Yamakami
    Theoretical Computer Science2015 568 1-18 2015 Refereed
  • Counting list matrix partitions of graphs
    Andreas Göbel, Leslie Ann Goldberg, Colin McQuillan, David Richerby, Tomoyuki Yamakami
    SIAM Journal on Computing 44(4) 1089-1118 2015 Refereed
  • Counting list matrix partitions of graphs
    Goebel, Goldberg, McQuillan, Richerby, Yamakami
    SIAM Journal on Computing 44(4) 1089-1118 2015 Refereed
  • Quantum state complexity of formal languages
    Marcos Villagra, Tomoyuki Yamakami
    Proceedings of the 17th International Workshop on Descriptional Complexity of Formal Systems (DCFS 2015), Lecture Notes in Computer Science 9118 280-291 Jun.  2015 Refereed
  • Complexity bounds of constant-space quantum computation (extended abstract)
    Tomoyuki Yamakami
    Proceedings of the 19th International Conference on Developments in Language Theory (DLT 2015), Lecture Notes in Computer Science 9168 426-438 Jul.  2015 Refereed
  • Straight construction of non-interactive quantum bit commitment schemes from indistinguishable quantum state ensembles
    Tomoyuki Yamakami
    Proceedings of the Fourth International Conference on Theory and Practice of Natural Computing (TPNC 2015), Lecture Notes in Computer Science 9477 121-133 Dec.  2015 Refereed
  • Interactive proofs with quantum finite automata
    Harumichi Nishimura, Tomoyuki Yamakami
    Theoretical Computer Science 568 1-18 Feb.  2015 Refereed
  • The world of combinatorial fuzzy problems and the efficiency of fuzzy approximation algorithms
    Tomoyuki Yamakami
    Proceedings of the Joint 7th International Conference on Soft Computing and Intelligent Systems and 15th International Symposium on Advanced Intelligent Systems 29-35 Dec.  2014 Refereed
  • Quantum and reversible verification of proofs using constant space
    Marcos Villagra, Tomoyuki Yamakami
    Proceedings of the 3rd International Conference on the Theory and Practice of Natural Computing 8890 144-156 Dec.  2014 Refereed
  • Not all multi-valued partial CFL functions are refined by single-valued functions (extended abstract)
    Tomoyuki Yamakami
    Proceedings of the IFIP Conference on Theoretical Computer Science, Lecture Notes in Computer Science 8705 136-150 Sep.  2014 Refereed
  • Structural complexity of multi-valued partial functions computed by nondeterministic pushdown automata (extended abstract)
    Tomoyuki Yamakami
    Proceedings of the 15th Italian Conference on Theoretical Computer Science, CEUR Workshop Proceedings 1231 225-236 Sep.  2014 Refereed
  • Counting List Matrix Partitions of Graphs
    A. Goebel, A. Goldberg, C. McQuillan, D. Richerby, T. Yamakami
    Proceedings of IEEE Computational Complexity Conference 56-65 Jun.  2014 Refereed
  • Oracle pushdown automata, nondeterministic reducibilities, and the hierarchy over the family of context-free languages
    Tomoyuki Yamakami
    Proceedings of the 40th International Conference on Current Trends in Theory and Practice of Computer Science, Lecture Notes in Computer Science 8327 514-525 Jan.  2014 Refereed
  • Constant unary constraints and symmetric real-weighted counting constraint satisfaction problems
    Tomoyuki Yamakami
    Theory of Computing Systems 55(1) 170-201 Jul.  2014 Refereed
  • Constant-space quantum interactive proof systems against multiple provers
    Tomoyuki Yamakami
    Information Processing Letters 114(11) 611-619 Nov.  2014 Refereed
  • One-way reversible and quantum finite automata with advice
    Tomoyuki Yamakami
    Information and Computation 239 122-148 Dec.  2014 Refereed
  • The dissecting power of regular languages
    Tomoyuki Yamakami, Yuichi Kato
    Information Processing Letters 113 116-122 Feb.  2013 Refereed
  • Uniform-circuit and logarithmic-space approximations of refined combinatorial optimization problems
    Tomoyuki Yamakami
    Proceedings of the 7th Annual International Conference on Combinatorial Optimization and Applications, Lecture Notes in Computer Science 8287 318-329 Dec.  2013 Refereed
  • Constant unary constraints and symmetric real-weighted counting CSPs
    Tomoyuki Yamakami
    Proceedings of the 23rd International Symposium on Algorithms and Computation (ISAAC 2012), Lecture Notes in Computer Science, Springer-Verlag 7676 237-246 Dec.  2012 Refereed
  • One-way reversible and quantum finite automata with advice
    Tomoyuki Yamakami
    Proceedings of the 6th International Conference on Language and Automata Theory and Applications (LATA 2012), lecture Notes in Computer Science 7183 526-537 Mar.  2012 Refereed
  • Approximate counting for complex-weighted Boolean constraint satisfaction problems
    Tomoyuki Yamakami
    Information and Computation 219 17-38 Oct.  2012 Refereed
  • Approximation complexity of complex-weighted degree-two counting constraint satisfaction problems
    Tomoyuki Yamakami
    Theoretical Computer Science 461 86-105 Nov.  2012 Refereed
  • A dichotomy theorem for the approximate counting of complex-weighted bounded-degree Boolean CSPs
    Tomoyuki Yamakami
    Theoretical Computer Science 447 120-135 Aug.  2012 Refereed
  • Computational indistinguishability between quantum states and its cryptographic application
    A. Kawachi, T. Koshiba, H. Nishimura, T. Yamakami
    Journal of Cryptology 25(3) 528-555 Jul.  2012 Refereed
  • Immunity and pseudorandomness of context-free languages
    Tomoyuki Yamakami
    Theoretical Computer Science 412(45) 6432-6450 Oct.  2011 Refereed
  • Optimization, randomized approximability, and Boolean constraint satisfaction problems
    Tomoyuki Yamakami
    Proceedings of the 22nd International Symposium on Algorithms and Computation (ISAAC 2011), Lecture Notes in Computer Science 7074 454-463 Dec.  2011 Refereed
  • Approximation complexity of complex-weighted degree-two counting constraint satisfaction problems (extended abstract)
    Tomoyuki Yamakami
    Proceedings of the 17th Annual International Computing and Combinatorics Conference (COCOON 2011), Lecture Notes in Computer Science 6842 122-133 Aug.  2011 Refereed
  • The roles of advice to one-tape linear-time Turing machines and finite automata (extended abstract)
    Tomoyuki Yamakami
    International Journal of Foundations of Computer Science 21(6) 941-962 Dec.  2010 Refereed
  • Quantum hardcore functions by complexity-theoretical quantum list decoding
    Akinori Kawachi, Tomoyuki Yamakami
    SIAM Journal on Computing 39(7) 2941-2969 2010 Refereed
  • Theory of one tape linear time Turing machines
    Kohtaro Tadaki, Tomoyuki Yamakami, Jack C. H. Lin
    Theoretical Computer Science 411(1) 22-43 Jan.  2010 Refereed
  • A trichotomy theorem for the approximate counting of complex-weighted bounded-degree Boolean CSPs
    Tomoyuki Yamakami
    Proceedings of the Fourth Annual International Conference on Combinatorial Optimization and Applications (COCOA 2010), Lecture Notes in Computer Science 6508 285-299 Dec.  2010 Refereed
  • Approximate counting for complex-weighted Boolean constraint satisfaction problems
    Tomoyuki Yamakami
    Proceedings of the Eighth Workshop on Approximation and Online Algorithms (WAOA 2010), Lecture Notes in Computer Science 6534 261-272 Sep.  2010 Refereed
  • Quantum Merlin-Arthur proof systems: are multiple Merlins more helpful to Arthur?
    Hirotada Kobayashi, Keiji Matsumoto, Tomoyuki Yamakami
    Chicago Journal of Theoretical Computer Science 2009 Article 3 Jul.  2009 Refereed
  • An application of quantum finite automata to interactive proof systems
    Harumichi Nishimura, Tomoyuki Yamakami
    Journal of Computer and System Sciences 75(4) 255-269 Jun.  2009 Refereed
  • The roles of advice to one-tape linear-time Turing machines and finite automata
    Tomoyuki Yamakami
    Proceedings of the Twentieth International Symposium on Algorithms and Computation (ISAAC 2009), Lecture Notes in Computer Science 5878 933-942 Dec.  2009 Refereed