Back to Yaoyun Shi's home page
Yaoyun Shi's Research Papers (more rencet papers are here)
 On multicast in quantum networks. With Emina Soljanin. 40th Annual Conference on Information Sciences and Systems (CISS) 2006.
 Path Auction Games When an Agent Can Own Multiple Edges. With Ye Du and Rahul Sami. NetEcon 2006.

Simulating quantum computation by contracting tensor networks. With
Igor Markov.

Classical simulation of quantum manybody systems with a tree tensornetwork.
Yaoyun Shi, Luming Duan, and Guifré Vidal.
 The communication complexity of the Hamming Distance Problem.
With Wei Huang, Shengyu Zhang, and Yufan Zhu. To appear in Information Processing Letters, 2006.

Tensor norms and the classical communication complexity of
bipartite quantum measurements.
Proceedings of the 37th ACM Symposium on Theory of Computing (STOC 2005),
460467, 2005.

Quantum and Classical Tradeoffs.
Theoretical Comptuer Science, 344(23):335 345, 2005.

Distributed construction of quantum fingerprints.
With Andris Ambainis,
Quantum Information and Computation, 4(2):146151, 2004.

Both Toffoli and ControlledNOT need little
help to do universal quantum computation.
Quantum Information and Computation, 3(1):8492, 2003.

Approximating linear restrictions of Boolean functions (Preliminary version).

Quantum lower bounds for the collision and the element distinctness problems.
Proceedings of the 43rd Annual Symposium on the Foundations of Computer Science
(FOCS 2002),
pp. 513519, 2002.
Journal version:
Journal of the ACM, 51(4):595605, 2004, joint with
Scott Aaronson.

Evasiveness of subgraph containment and related properties.
With Amit Chakrabarti and Subhash Khot,
SIAM Journal on Computing, 31(3), 2002, pp. 866875.

Informational complexity and the direct sum
problem for simultaneous message complexity.
With Amit Chakrabarti, Anthony Wirth, and Andrew Yao,
Proceedings of the FortySecond Annual
Symposium on Foundations of Computer Science (FOCS 2001),
pp. 270278, 2001.

Quantum complexities of ordered searching,
sorting, and element distinctness.
With Peter Høyer and Jan Neerbek,
Algorithmica, 34(4), pp. 429448, 2002.

Entropy lower bounds of quantum decision tree complexity.
Information Processing Letters, 81(1), 2002.

Lower bounds of quantum blackbox complexity and degree of
approximating polynomials by influence of Boolean variables.
Information Processing Letters, 75(12):7983, July 2000.