Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

All reports by Author Tomoyuki Yamakami:

TR06-020 | 10th February 2006
Akinori Kawachi, Tomoyuki Yamakami

Quantum Hardcore Functions by Complexity-Theoretical Quantum List Decoding

Revisions: 1

We present three new quantum hardcore functions for any quantum one-way function. We also give a "quantum" solution to Damgard's question (CRYPTO'88) on his pseudorandom generator by proving the quantum hardcore property of his generator, which has been unknown to have the classical hardcore property.
Our technical tool is ... more >>>

TR04-110 | 24th November 2004
Tomoyuki Yamakami, Harumichi Nishimura

An Application of Quantum Finite Automata to Interactive Proof Systems

Quantum finite automata have been studied intensively since
their introduction in late 1990s as a natural model of a
quantum computer with finite-dimensional quantum memory space.
This paper seeks their direct application
to interactive proof systems in which a mighty quantum prover
communicates with a ... more >>>

TR04-066 | 6th July 2004
Tomoyuki Yamakami, Toshio Suzuki

Resource Bounded Immunity and Simplicity

Revisiting the thirty years-old notions of resource-bounded immunity and simplicity, we investigate the structural characteristics of various immunity notions: strong immunity, almost immunity, and hyperimmunity as well as their corresponding simplicity notions. We also study limited immunity and simplicity, called k-immunity and feasible k-immunity, and their simplicity notions. Finally, we ... more >>>

TR03-059 | 18th May 2003
Harumichi Nishimura, Tomoyuki Yamakami

Polynomial time quantum computation with advice

Revisions: 2

Advice is supplementary information that enhances the computational
power of an underlying computation. This paper focuses on advice that
is given in the form of a pure quantum state. The notion of advised
quantum computation has a direct connection to non-uniform quantum
circuits and tally languages. The paper examines the ... more >>>

TR98-073 | 14th December 1998
Tomoyuki Yamakami, Andrew Chi-Chih Yao

NQP = co-C_{=}P

Revisions: 2

Adleman, DeMarrais, and Huang introduced the
nondeterministic quantum polynomial-time complexity class NQP as an
analogue of NP. It is known that, with restricted amplitudes, NQP is
characterized in terms of the classical counting complexity class
C_{=}P. In this paper we prove that, with unrestricted amplitudes,
NQP indeed coincides with the ... more >>>

TR95-039 | 11th July 1995
Tomoyuki Yamakami

Polynomial Time Samplable Distributions

Revisions: 2

This paper studies distributions which
can be ``approximated'' by sampling algorithms in time polynomial in
the length of their outputs. First, it is known that if
polynomial-time samplable distributions are polynomial-time
computable, then NP collapses to P. This paper shows by a simple
... more >>>

ISSN 1433-8092 | Imprint