Quantum Computation and Quantum Information
On characterizing
quantum correlated equilibria
Zhaohui Wei, Shengyu Zhang
Manuscript, 2011.
A quantum protocol
for sampling correlated equilibria unconditionally and without a mediator
Iordanis Kerenidis, Shengyu Zhang
Manuscript, 2011.
Quantum Strategic
Game Theory
Shengyu Zhang
The 3rd Innovations in
Theoretical Computer Science (ITCS), 2012, too appear. Also presented
at QIP'11. (Slides)
On the power
of lower bound methods for quantum one-way communication complexity
Shengyu
Zhang
Proceedings of the
38th International Colloquium on Automata, Languages and Programming (ICALP),
pp. 49-60, 2011. (Slides)
Composition theorems in
communication complexity
Troy Lee, Shengyu Zhang
Proceedings of the
37th International Colloquium on Automata, Languages and Programming (ICALP),
pp. 475-489, 2010.
On the power
of a unique quantum witness
Rahul Jain, Iordanis Kerenidis, Greg Kuperberg, Miklos Santha, Or Sattath, Shengyu Zhang
Proceedings of the
First Symposium on Innovations in Computer Science (ICS),
pp. 470-481, 2010. (Slides)
(Earlier version in QIP'10)
A Survey of
BQP-Completeness
Shengyu
Zhang
Invited book chapter, Handbook of Natural
Computing, Springer-Verlag, 2010.
Any AND-OR
formula of size N can be evaluated in time N1/2+o(1) on a quantum
computer
Andris Ambainis, Andrew Childs, Ben
Reichardt, Robert
Spalek, Shengyu Zhang
SIAM Journal on Computing, Volume 39, Issue
6 (special issue for FOCS'07), pp. 2513-2530, 2010. (Earlier version in
FOCS'07 and QIP'08)
(Merge of independent results
by the first author and
by the rest authors.)
Tight bounds for randomized and quantum Local Search
Shengyu Zhang
SIAM Journal on Computing, Volume 39, Issue 3,
pp 948-977, 2009. (Earlier version
in STOC'06.)
Note on quantum counting classes
Yaoyun Shi, Shengyu Zhang
Manuscript, 2009.
New bounds
on classical and quantum one-way communication complexity
Rahul
Jain, Shengyu Zhang
Theoretical Computer Science, 410 (26), pp.
2463-2477, 2009.
Making classical honest verifier zero
knowledge protocols secure against quantum attacks
Sean Hallgren, Alexandra
Kolla, Pranab
Sen, Shengyu Zhang
Proceedings of the 35th International Colloquium on Automata, Languages and
Programming (ICALP), pp. 592-603, 2008. (Earlier version
in QIP'07)
(Best paper award of track C.)
Measuring energy of basis
states in translationally invariant nearest-neighbor interactions in qudit
chains is universal for quantum computing
Dominik
Janzing, Pawel Wocjan, Shengyu Zhang
New Journal of Physics,
(10) 093004, 2008.
Several
natural BQP-complete problems
Pawel
Wocjan, Shengyu Zhang
Manuscript, quant-ph/0606179, 2006.
The
quantum query complexity, the approximate degree and the total influence
Yaoyun Shi, Shengyu Zhang
Manuscript, 2005.
Promised and
distributed quantum search
Shengyu Zhang
Proceedings
of the 11th International Computing and Combinatorics Conference (COCOON),
pp. 430-439, 2005.
On the power of Ambainis lower
bounds
Shengyu
Zhang
Theoretical Computer Science, 339(2-3), pp. 241-256, 2005. (Earlier version in
ICALP'04, invited to TCS)
Graph
properties and circular functions: how low can quantum query complexity go?
Xiaoming Sun, Andrew
Yao, Shengyu Zhang
Proceedings of
the19th Annual IEEE Conference on Computational Complexity (CCC), pp.
286-293, 2004.
Lower
bound on inconclusive probability of unambiguous discrimination
Yuan
Feng,
Shengyu
Zhang, Runyao Duan,
Mingsheng Ying
Physical Review A, 66, 062313, December
2002.
Set discrimination of quantum states
Shengyu
Zhang, Mingsheng
Ying
Physical Review
A, 65, 062322, June 2002.
Universal
and original-preserving quantum copying is impossible
Yuan
Feng, Shengyu Zhang,
Xiaoming Sun,
Mingsheng Ying
Physics Letters
A, 297(1-2), pp. 1-3, 2002.
Mathematical
nature of and a family of lower bounds for the success probability of
unambiguous discrimination
Xiaoming Sun, Shengyu
Zhang, Yuan Feng, Mingsheng
Ying
Physical
Review A, 65, 044306, April 2002.
Probabilistic
cloning and deleting of quantum states
Yuan
Feng,
Shengyu
Zhang, Mingsheng Ying
Physical
Review A, 65, 042324, April 2002.
Upper
bound for the success probability of unambiguous discrimination among quantum
states
Shengyu Zhang, Yuan
Feng,
Xiaoming Sun, Mingsheng
Ying
Physical Review
A, 64, 062103, November 2001.
Complexity theory
The influence lower
bound via query elimination
Rahul
Jain, Shengyu Zhang
Theory of Computing, Volume
7, pp. 147-153, 2011.
Tight bounds on the
communication complexity of symmetric XOR functions in one-way and SMP
models
Ming Lam Leung, Yang Li,
Shengyu Zhang
Proceedings of the 8th Annual Conference on
Theory and Applications of Models of Computation (TAMC), 403-408,
2011.
Depth-Independent
Lower bounds on the Communication Complexity of Read-Once Boolean Formulas
Rahul
Jain, Hartmut Klauck, Shengyu Zhang
Proceedings of the 16th Annual
International Computing and Combinatorics Conference (COCOON), pp.
54-59, 2010.
On
the tightness of the Buhrman-Cleve-Wigderson simulation
Shengyu Zhang
Proceedings of the 20th International Symposium on Algorithms and
Computation (ISAAC), pp.
434-440, 2009.
(Slides)
How
many rounds can Random Selection handle to obtain general zero-knowledge
protocols?
Shengyu
Zhang
Information Processing Letters, accepted.
The
communication complexity of the Hamming Distance problem
Wei Huang,
Yaoyun Shi,
Shengyu Zhang, Yufan Zhu
Information
Processing Letters, 99(4), pp.
149-153, 2006.
On the average sensitivity of monotone Boolean functions
Shengyu Zhang
Manuscript, 2004.
Applied Algorithms
Combinatorial algorithms for nearest neighbors, near-duplicates and
small-world design
Yury Lifshits, Shengyu Zhang
Proceedings of the 20th Annual ACM-SIAM Symposium
on Discrete Algorithms (SODA), pp. 318-326, 2009.
Information diffusion on a
circle
Xiaojie Gao, Kevin Ko, Shengyu Zhang
Manuscript, 2008.
Streaming
algorithms measured in terms of the computed quantity
Shengyu Zhang
Proceedings of the 11th International
Computing and Combinatorics Conference (COCOON), pp. 338-348, 2007.
Distributed
rate allocation for inelastic flows
Prashanth
Hande, Shengyu Zhang, Mung
Chiang
IEEE/ACM Transactions on Networking, vol. 15, no. 6, pp. 1240-1253, December 2007.
(Journal version of the
INFOCOM’05 paper below, but with significant additions beyond the conference version.)
Distributed
rate allocation for inelastic flows: optimization frameworks, optimality
conditions and optimal algorithms
Mung Chiang, Shengyu Zhang, Prashanth
Hande
Proceedings of the 23rd Annual
Joint Conference of the IEEE Computer and Communications Societies (INFOCOM),
pp. 2679-2690, 2005.
Others
Research on
version backtracking in cooperative design
Xiang Cao, Shengyu
Zhang, Guoqin Zheng,
Jiaguang Sun
Proceedings of the
7th International Conference on Computer Aided Design and Computer Graphics, Volume 2, pp. 656-661, 2001.
Action reliability of
probabilistic transition systems
Shengyu Zhang,
Mingsheng
Ying
Manuscript,
2001.