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
Classical simulation of quantum many-body 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),
Quantum and Classical Tradeoffs.
Theoretical Comptuer Science, 344(2-3):335 345, 2005.
Distributed construction of quantum fingerprints.
With Andris Ambainis,
Quantum Information and Computation, 4(2):146-151, 2004.
Both Toffoli and Controlled-NOT need little
help to do universal quantum computation.
Quantum Information and Computation, 3(1):84-92, 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
pp. 513-519, 2002.
Journal of the ACM, 51(4):595-605, 2004, joint with
Evasiveness of subgraph containment and related properties.
With Amit Chakrabarti and Subhash Khot,
SIAM Journal on Computing, 31(3), 2002, pp. 866-875.
Informational complexity and the direct sum
problem for simultaneous message complexity.
With Amit Chakrabarti, Anthony Wirth, and Andrew Yao,
Proceedings of the Forty-Second Annual
Symposium on Foundations of Computer Science (FOCS 2001),
pp. 270-278, 2001.
Quantum complexities of ordered searching,
sorting, and element distinctness.
With Peter Høyer and Jan Neerbek,
Algorithmica, 34(4), pp. 429-448, 2002.
Entropy lower bounds of quantum decision tree complexity.
Information Processing Letters, 81(1), 2002.
Lower bounds of quantum black-box complexity and degree of
approximating polynomials by influence of Boolean variables.
Information Processing Letters, 75(1-2):79-83, July 2000.