Yaoyun Shi （施尧耘，施堯耘）

Associate Professor
Ph.D., Princeton, 2001; B.S., Beijing University, 1997.

Contact information:
Postal: University of Michigan, Electrical Engineering and Computer Science, 2260 Hayward, Ann Arbor, MI 48109-2121, USA
Office: CSE 3632, Telephone: (734)764-3308, Fax: (734)763-1260.
E-mail:

Research Interests: theory of computation and quantum computing.

My research aims to understand the inherent power and limitations of various computing technologies, including those currently deployed, as well as more recent paradigms such as quantum mechanical computation. The techniques involved come from many branches of mathematics, such as combinatorics, linear algebra, probability theory, and approximation theory.

For example, with Høyer and Neerbek, I proved that quantum computers cannot substantially outperform classical computers for sorting numbers. Lately, I have been trying to develop fast algorithms for systematic classical simulations of quantum computation and the evolution of quantum systems. Such algorithms will not only sharpen the boundary between quantum and classical computations, but may also provide powerful tools for the analysis and engineering of quantum information processing components.

Working with my students and colleagues, I am also developing interest on several other topics, such as biological information processing, computational game theory, and natural language processing.

My research has been partly funded by US National Science Foundation.

• Research activities and findings under NSF 0622033, Some theory problems on quantum computation and information.

Recent Papers

• Tripartite to bipartite entanglement transformations and Polynomial Identity Testing. With Eric Chitambar and Runyao Duan, 2009.
• Predicting stock returns and fund performance through network analysis. With Noah Stoffman, Kathy Yuan, and Ji Zhu.
• Constant-degree graph expansions that preserve treewidth. With Igor Markov. To appear in Algorithmica, 2009.
• The quantum communication complexity of block-composed functions. With Yufan Zhu. Quantum Information and Computation, 9(5&6):444-460, 2009.
• Communication complexities of XOR functions. With Zhiqiang Zhang. Quantum Information and Computation, 9(3&4): 255-254, 2009.
• PerturbationRank: a non-monotone ranking algorithm. With Ye Du and James Leung.
• Tripartite entanglement transformations and tensor rank With Eric Chitambar and Runyao Duan, Physical Review Letters,101, 140502, 2008.
• Entanglement between two uses of a noisy multipartite quantum channel enables perfect transmission of classical information. With Runyao Duan. Physical Review Letters, 101, 020501, 2008.
• Characterizing locally indistinguishable orthogonal product states. With Yuan Feng, IEEE Transactions on Information Theory, 55(6), 2799--2806, 2009.
• Approximate polynomial degree of Boolean functions and its applications. Proceedings of the 4th International Congress of Chinese Mathematicians, 2007.
• Simulating quantum computation by contracting tensor networks. With Igor Markov. SIAM Journal on Computing, 38(3):963-981, 2008.
• Using Spam Farm to Boost PageRank. With Ye Du and Xin Zhao. Proceedings of Third International Workshop on Adversarial Information Retrieval on the Web ( AIRWeb07), 2007.
• 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.
• Classical simulation of quantum many-body systems with a tree tensor network. Yaoyun Shi, Luming Duan, and Guifré Vidal, Physical Review A, 74, 022320, 2006.
• The communication complexity of the Hamming Distance Problem. With Wei Huang, Shengyu Zhang, and Yufan Zhu. Information Processing Letters, 99(4), 149--153, 2006.
• Tensor norms and the classical communication complexity of bipartite quantum measurements. With Yufan Zhu, SIAM Journal on Computing, 38(3):753--766, 2008. A preliminary version appeared in Proceedings of the 37th ACM Symposium on Theory of Computing (STOC 2005), 460--467, 2005.
• Quantum and Classical Tradeoffs. Theoretical Computer Science, 344(2-3):335 345, 2005.

Older Papers

You are visiting me from 38.107.191.107