Back to Yaoyun Shi's home page

Yaoyun Shi's Research Papers

• 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 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), 460--467, 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 (FOCS 2002), pp. 513-519, 2002. Journal version: Journal of the ACM, 51(4):595-605, 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. 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.