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

__
TR02-074
| 26th December 2002
__

Andrew Chi-Chih Yao#### On the Power of Quantum Fingerprinting

__
TR02-062
| 19th November 2002
__

Andrew Chi-Chih Yao#### Classical Physics and the Church-Turing Thesis

__
TR98-073
| 14th December 1998
__

Tomoyuki Yamakami, Andrew Chi-Chih Yao#### NQP = co-C_{=}P

Revisions: 2

Fan Chung, Ron Graham, Jia Mao, Andrew Chi-Chih Yao

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

Andrew Chi-Chih Yao

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

Andrew Chi-Chih Yao

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

Tomoyuki Yamakami, Andrew Chi-Chih Yao

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