Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

All reports by Author Andrew Chi-Chih Yao:

TR03-078 | 23rd October 2003
Fan Chung, Ron Graham, Jia Mao, Andrew Chi-Chih Yao

Finding Favorites

Comments: 2

We investigate a new type of information-theoretic identification problem, suggested to us by Alan Taylor. In this problem we are given a set of items, more than half of which share a common ``good" value. The other items have various other values which are called ``bad". The only method we ... more >>>

TR02-074 | 26th December 2002
Andrew Chi-Chih Yao

On the Power of Quantum Fingerprinting

In the simultaneous message model, two parties holding $n$-bit integers
$x,y$ send messages to a third party, the {\it referee}, enabling
him to compute a boolean function $f(x,y)$. Buhrman et al
[BCWW01] proved the remarkable result that, when $f$ is the
equality function, the referee can solve this problem by ... more >>>

TR02-062 | 19th November 2002
Andrew Chi-Chih Yao

Classical Physics and the Church-Turing Thesis

Would physical laws permit the construction of computing machines
that are capable of solving some problems much faster than the
standard computational model? Recent evidence suggests that this
might be the case in the quantum world. But the question is of
great interest even in the realm of classical physics. ... 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 >>>

ISSN 1433-8092 | Imprint