# Yaoyun Shi

According to our database

Collaborative distances:

^{1}, Yaoyun Shi authored at least 35 papers between 2000 and 2018.Collaborative distances:

## Timeline

#### Legend:

Book In proceedings Article PhD thesis Other## Links

#### On csauthors.net:

## Bibliography

2018

Limitations on transversal computation through quantum homomorphic encryption.

Quantum Information & Computation, 2018

2017

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

SIAM J. Comput., 2017

Randomness in nonlocal games between mistrustful players.

Quantum Information & Computation, 2017

2016

Quantum Algorithm for the Parity Problem.

Encyclopedia of Algorithms, 2016

Robust Protocols for Securely Expanding Randomness and Distributing Keys Using Untrusted Quantum Devices.

J. ACM, 2016

2015

Epsilon-net method for optimizations over separable states.

Theor. Comput. Sci., 2015

2013

Efficient Protocols for Generating Bipartite Classical Distributions and Quantum States.

IEEE Trans. Information Theory, 2013

Optimal Robust Self-Testing by Binary Nonlocal XOR Games.

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

2012

Quantum Simpsons Paradox and High Order Bell-Tsirelson Inequalities

CoRR, 2012

Correlation/Communication complexity of generating bipartite states

CoRR, 2012

2011

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

Quantum Information & Computation, 2011

Constant-Degree Graph Expansions that Preserve Treewidth.

Algorithmica, 2011

2010

On the parity complexity measures of Boolean functions.

Theor. Comput. Sci., 2010

Path auctions with multiple edge ownership.

Theor. Comput. Sci., 2010

When is there a multipartite maximum entangled state?

Quantum Information & Computation, 2010

2009

Characterizing locally indistinguishable orthogonal product states.

IEEE Trans. Information Theory, 2009

Communication complexities of symmetric XOR functions.

Quantum Information & Computation, 2009

Quantum communication complexity of block-composed functions.

Quantum Information & Computation, 2009

2008

Quantum Algorithm for the Parity Problem.

Proceedings of the Encyclopedia of Algorithms - 2008 Edition, 2008

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

SIAM J. Comput., 2008

Simulating Quantum Computation by Contracting Tensor Networks.

SIAM J. Comput., 2008

Communication Complexities of XOR functions

CoRR, 2008

2007

Using Spam Farm to Boost PageRank.

Proceedings of the AIRWeb 2007, 2007

2006

The communication complexity of the Hamming distance problem.

Inf. Process. Lett., 2006

2005

Quantum and classical tradeoffs.

Theor. Comput. Sci., 2005

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

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

2004

Distributed construction of quantum fingerprints.

Quantum Information & Computation, 2004

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

J. ACM, 2004

2003

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

Quantum Information & Computation, 2003

2002

Entropy lower bounds for quantum decision tree complexity.

Inf. Process. Lett., 2002

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

Algorithmica, 2002

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

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

2001

Evasiveness of Subgraph Containment and Related Properties.

SIAM J. Comput., 2001

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

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.

Inf. Process. Lett., 2000