Yaoyun Shi

According to our database, Yaoyun Shi authored at least 39 papers between 2000 and 2023.

Collaborative distances:

• Dijkstra number of three.
• Erdős number of three.

2023

A Classical Architecture For Digital Quantum Computers.

Fang Zhang, Xing Zhu, Rui Chao, Cupjin Huang, Linghang Kong, Guoyang Chen, Dawei Ding, Haishan Feng, Yihuai Gao, Xiaotong Ni, Liwei Qiu, Zhe Wei, Yueming Yang, Yang Zhao, Yaoyun Shi, Weifeng Zhang, Peng Zhou, Jianxin Chen

CoRR, 2023

2021

Efficient parallelization of tensor network contraction for simulating quantum computation.

Cupjin Huang, Fang Zhang, Michael Newman, Xiaotong Ni, Dawei Ding, Junjie Cai, Xun Gao, Tenghui Wang, Feng Wu, Gengyan Zhang, Hsiang-Sheng Ku, Zhengxiong Tian, Junyin Wu, Haihong Xu, Huanjun Yu, Bo Yuan, Mario Szegedy, Yaoyun Shi, Hui-Hai Zhao, Chunqing Deng, Jianxin Chen

Nat. Comput. Sci., 2021

2020

Parallel Device-Independent Quantum Key Distribution.

Rahul Jain, Carl A. Miller, Yaoyun Shi

IEEE Trans. Inf. Theory, 2020

2018

Limitations on transversal computation through quantum homomorphic encryption.

Michael Newman, Yaoyun Shi

Quantum Inf. Comput., 2018

2017

Universal Security for Randomness Expansion from the Spot-Checking Protocol.

Carl A. Miller, Yaoyun Shi

SIAM J. Comput., 2017

Randomness in nonlocal games between mistrustful players.

Carl A. Miller, Yaoyun Shi

Quantum Inf. Comput., 2017

2016

Quantum Algorithm for the Parity Problem.

Yaoyun Shi

Encyclopedia of Algorithms, 2016

2014

Robust protocols for securely expanding randomness and distributing keys using untrusted quantum devices.

Carl A. Miller, Yaoyun Shi

Proceedings of the Symposium on Theory of Computing, 2014

2013

Optimal Robust Self-Testing by Binary Nonlocal XOR Games.

Carl A. Miller, Yaoyun Shi

Proceedings of the 8th Conference on the Theory of Quantum Computation, 2013

Efficient protocols of generating bipartite classical distributions and quantum states.

Rahul Jain, Yaoyun Shi, Zhaohui Wei, Shengyu Zhang

Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, 2013

2012

Quantum Simpsons Paradox and High Order Bell-Tsirelson Inequalities

Yaoyun Shi

CoRR, 2012

Correlation/Communication complexity of generating bipartite states

Rahul Jain, Yaoyun Shi, Zhaohui Wei, Shengyu Zhang

CoRR, 2012

Epsilon-Net Method for Optimizations over Separable States.

Yaoyun Shi, Xiaodi Wu

Proceedings of the Automata, Languages, and Programming - 39th International Colloquium, 2012

2011

Deciding unitary equivalence between matrix polynomials and sets of bipartite quantum states.

Eric Chitambar, Carl A. Miller, Yaoyun Shi

Quantum Inf. Comput., 2011

Constant-Degree Graph Expansions that Preserve Treewidth.

Igor L. Markov, Yaoyun Shi

Algorithmica, 2011

2010

On the parity complexity measures of Boolean functions.

Zhiqiang Zhang, Yaoyun Shi

Theor. Comput. Sci., 2010

Path auctions with multiple edge ownership.

Ye Du, Rahul Sami, Yaoyun Shi

Theor. Comput. Sci., 2010

When is there a multipartite maximum entangled state?

Runyao Duan, Yaoyun Shi

Quantum Inf. Comput., 2010

2009

Characterizing locally indistinguishable orthogonal product states.

Yuan Feng, Yaoyun Shi

IEEE Trans. Inf. Theory, 2009

Communication complexities of symmetric XOR functions.

Zhiqiang Zhang, Yaoyun Shi

Quantum Inf. Comput., 2009

Quantum communication complexity of block-composed functions.

Yaoyun Shi, Yufan Zhu

Quantum Inf. Comput., 2009

2008

Quantum Algorithm for the Parity Problem.

Yaoyun Shi

Proceedings of the Encyclopedia of Algorithms - 2008 Edition, 2008

Tensor Norms and the Classical Communication Complexity of Nonlocal Quantum Measurement.

Yaoyun Shi, Yufan Zhu

SIAM J. Comput., 2008

Simulating Quantum Computation by Contracting Tensor Networks.

Igor L. Markov, Yaoyun Shi

SIAM J. Comput., 2008

Communication Complexities of XOR functions

Yaoyun Shi, Zhiqiang Zhang

CoRR, 2008

2007

Using Spam Farm to Boost PageRank.

Ye Du, Yaoyun Shi, Xin Zhao

Proceedings of the AIRWeb 2007, 2007

2006

The communication complexity of the Hamming distance problem.

Wei Huang, Yaoyun Shi, Shengyu Zhang, Yufan Zhu

Inf. Process. Lett., 2006

On Multicast in Quantum Networks.

Yaoyun Shi, Emina Soljanin

Proceedings of the 40th Annual Conference on Information Sciences and Systems, 2006

2005

Tensor norms and the classical communication complexity of nonlocal quantum measurement.

Yaoyun Shi

Proceedings of the 37th Annual ACM Symposium on Theory of Computing, 2005

2004

Distributed construction of quantum fingerprints.

Andris Ambainis, Yaoyun Shi

Quantum Inf. Comput., 2004

Quantum lower bounds for the collision and the element distinctness problems.

Scott Aaronson, Yaoyun Shi

J. ACM, 2004

Quantum and Classical Tradeoffs

Yaoyun Shi

Electron. Colloquium Comput. Complex., 2004

2003

Both Toffoli and controlled-NOT need little help to do universal quantum computing.

Yaoyun Shi

Quantum Inf. Comput., 2003

2002

Entropy lower bounds for quantum decision tree complexity.

Yaoyun Shi

Inf. Process. Lett., 2002

Quantum Lower Bounds for the Collision and the Element Distinctness Problems.

Yaoyun Shi

Proceedings of the 43rd Symposium on Foundations of Computer Science, 2002

2001

Evasiveness of Subgraph Containment and Related Properties.

Amit Chakrabarti, Subhash Khot, Yaoyun Shi

Proceedings of the STACS 2001, 2001

Quantum Complexities of Ordered Searching, Sorting, and Element Distinctness.

Peter Høyer, Jan Neerbek, Yaoyun Shi

Proceedings of the Automata, Languages and Programming, 28th International Colloquium, 2001

Informational Complexity and the Direct Sum Problem for Simultaneous Message Complexity.

Amit Chakrabarti, Yaoyun Shi, Anthony Wirth, Andrew Chi-Chih Yao

Proceedings of the 42nd Annual Symposium on Foundations of Computer Science, 2001

2000

Lower bounds of quantum black-box complexity and degree of approximating polynomials by influence of Boolean variables.

Yaoyun Shi

Inf. Process. Lett., 2000