Tomoyuki Yamakami

My Past Research

(*) This page consists of almost all papers that I have written since 1984.

Recent Publication List (DBLP database)

Recent Paper Manuscripts (


(*) Lecture Notes 2018 about My Past Research (only on complexity theory)

Lecture 1 - Basic Computation Models

Lecture 2 - NP-Completeness, Probabilistic and Counting Complexity Classes

Lecture 3 - Space-Bounded Complexity and the Linear Space Hypothesis

Lecture 4 - Relativizations and Hierarchies

Lecture 5 - Structural Properties by Finite Automata

Lecture 6 - Type-2 Computability, Multi-Valued Functions, and State Complexity

Lecture 7 - Cryptographic Concepts for Finite Automata

Lecture 8 - Constraint Satisfaction Problems

Lecture 9 - Combinatorial Optimization Problems

lecture 10 - Average-Case Complexity

Lecture 11 - Basics of Quantum Information

Lecture 12 - BQP, NQP, Quantum NP, and Quantum Finite Automata

Lecture 13 - Quantum State Complexity and Advice

Lecture 14 - Quantum Cryptographic Systems

Lecture 15 - Quantum Interactive Proofs



(*) The following papers are not listed in the above DBLP database.


Refereed Journal Publications: Published

 T. Yamakami. Quantum list decoding of classical block codes of polynomially small rate from quantumly corrupted codewords. Baltic Journal of Modern Computing, Vol.4(4), pp.753-788, 2016.

 M. Takano and T. Yamakami. Classification of intermediate predicate logics under the type of deductive completeness. Reports on Mathematical Logic, Vol.24, pp.17-23, 1990.


Refereed Contributions: Conference Proceedings

 K. Iwama, R. Raymond H.P., S. Yamashita, and T. Yamakami. Quantum complexity of noisy IP query. The 2nd ERATO Workshop on Quantum Information Science (EQIS'02), September 2002.

 T. Yamakami. Computational complexity of languages counting random oracles. Lecture Notes in Mathematics, Springer-Verlag, Vol.1388, pp.189-202, 1989.


Poster Presentation: Poster Session

 A. Kawachi, T. Koshiba, H. Nishimura, and T. Yamakami. A quantum trapdoor one-way function that relies on the hardness of the graph automorphism problem. The 3rd ERATO Conference on Quantum Information (EQIS'03), Kyoto, September 4-6, 2003.

 H. Nishimura, T. Yamakami, and A. Kawachi. Complexity of quantum generation and distinguishability. The 4th Annual Conference on Mathematics of Information Technology and Complex Systems (MITACS'03), Ottawa, May 8-10, 2003.

 K. Iwama, R. Raymond H.P., S. Yamashita, and T. Yamakami. Quantum complexity of noisy IP query. The 6th Annual Symposium on Quantum Information Technology (QIT'02), Kyoto, May 2002.


Non-Refereed Contributions: Technical Reports and Recently Submitted Papers

 T. Yamakami. Multiple quantum zer-knowledge proofs with constant-space verifiers. Unpublished manuscript, 2005.

 A. Balyuk and T. Yamakami. Theory and applications of counting circuits. Unpublished manuscript, June, 2004.

 T. Yamakami. Theory and applications of limited quantumization. Unpublished manuscript, July, 2002.

 T. Yamakami. A recursive definition of quantum polynomial time. Unpublished manuscript, 2001.

 T. Yamakami. Uniform AC0 counting circuits. Unpublished manuscript, University of Toronto, November, 1996.

 T. Yamakami. Simplicity. Unpublished manuscript, University of Toronto, 1995.

 T. Yamakami. Polynomial helpers of robust machines. Technical Report, Gunma University, 1990.



 Cardinal number theory. Undergraduate Graduation Thesis, University of Tsukuba, 1984.

 On logic related to Prior's modal calculus Q. Master's Thesis, Shizuoka University, 1986.

 Average case computational complexity theory. Ph.D. Thesis, University of Toronto, 1997. Technical Report 307/97, University of Toronto. See also ECCC Thesis Listings.