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 (arXiv.org)

 

(*) 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.

 

Theses

· 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.

Researcher

TomoyukiYamakami.INFO