Quantum game players can have advantage without discord
Zhaohui Wei and Shengyu Zhang
Information and Computation, 2017. (Slides)
Learning to Aggregate Ordinal Labels by Maximizing Separating Width
Guangyong Chen, Shengyu Zhang*, Di Lin, Hui Huang, Pheng Ann Heng
Proceedings of the 34th International Conference on Machine Learning (ICML), 2017.
Networked Fairness in Cake Cutting
Xiaohui Bei, Youming Qiao, Shengyu Zhang
Proceedings of the 26th International Joint Conference on Artificial Intelligence (IJCAI), 2017.
(Slides)
Online Roommate Allocation Problem
Guangda Huzhang, Xin Huang, Shengyu Zhang, Xiaohui Bei
Proceedings of the 26th International Joint Conference on Artificial Intelligence (IJCAI), 2017.
Sensitivity Conjecture and Log-rank Conjecture for functions with small alternating numbers
Chengyu Lin and Shengyu Zhang
Proceedings of the 44th International Colloquium on Automata, Languages, and Programming (ICALP), 2017.
(Slides)
Fast quantum algorithms for Least Squares Regression and Statistic Leverage Scores
Yang liu and Shengyu Zhang
Theoretical Computer Science , volume 657 (special issue
for FAW'15), pages 38-47, 2017.
(Slides)
On the complexity of probabilistic trials for hidden satisfiability problems
Itai Arad, Adam Bouland, Daniel Grier, Miklos Santha, Aarthi Sundaram and Shengyu Zhang
Proceedings of the 41st International Symposium on
Mathematical Foundations of Computer Science (MFCS), pages 12:1-12:14, 2016.
Contextual Combinatorial Cascading Bandits
Shuai Li, Baoxiang Wang, Shengyu Zhang, Wei Chen
Proceedings of the 33rd International Conference on Machine Learning (ICML),
pages 1245-1253, 2016.
Linear time algorithm for quantum 2SAT
Itai Arad, Miklos Santha, Aarthi Sundaram, Shengyu Zhang
Proceedings of the 43rd International Colloquium on Automata, Languages and Programming (ICALP), pages 15:1-15:14, 2016.
(Slides)
Earlier at QIP'16.
Multipartite Quantum Correlation and Communication Complexities
Rahul Jain, Zhaohui Wei, Penghui Yao, Shengyu Zhang
Computational complexity, page 1-30, May 2016.
Fourier Sparsity of GF(2) Polynomials
Hing Yin Tsang, Ning Xie, Shengyu Zhang
Proceedings of the 11th International Computer Science Symposium in Russia (CSR), pages 409-424, 2016.
Semiquantum key distribution with secure delegated quantum computation
Qin Li, Wai Hong Chan, Shengyu Zhang
Scientific Reports, 6, Article no. 19898, 2016.
Assignment and Pricing in Roommate Market
Pak Hay Chan, Xin Huang, Zhengyang Liu, Chihao Zhang, Shengyu Zhang
Proceedings of the Thirtieth AAAI Conference on Artificial Intelligence (AAAI),
oral presentation, pages 446-452, 2016. (Slides)
Trial and Error Algorithms
Xiaohui Bei, Ning Chen, Shengyu Zhang
Encyclopedia of Algorithms, book chapter, pages 2258-2261, 2016.
A Semantic Hash Tree Based Verifiable Data Access Protocol on the Cloud
Fei Chen, Tao Xiang, Jianyong Chen, Xinwen Fu, Wei Yu, Shengyu Zhang
Proceedings of the Third International Conference on Advanced Cloud and Big Data
(CBD), pages 219-226, 2015.
Fast Relative-Error Approximation Algorithm for Ridge Regression
Shouyuan Chen, Yang Liu, Michael R. Lyu, Irwin King, Shengyu Zhang
Proceedings of the 31st Conference on Uncertainty in Artificial Intelligence (UAI), pages 201-210, 2015.
Solving linear programming with constraints unknown
Xiaohui Bei, Ning Chen, Shengyu Zhang
Proceedings of the 42nd International Colloquium on Automata, Languages, and Programming (ICALP),
pages 129-142, 2015.
Social Models and Algorithms for Optimization of Contact Immunity of Oral Polio Vaccine
Chengwei Guo, Chenglong Ma, Shengyu Zhang
Proceedings of the 9th International Frontiers of Algorithmics Workshop (FAW),
pages 66-77, 2015.
Secure Cloud Storage Hits Distributed String Equality Checking:
More Efficient, Conceptually Simpler, and Provably Secure
Fei Chen, Tao Xiang, Yuanyuan Yang, Cong Wang, Shengyu Zhang
Proceedings of the IEEE Conference on Computer
Communications (INFOCOM), pages 2389-2397, 2015.
On
the I/O Complexity of Dynamic Distinct Counting
Xiaocheng Hu, Yufei Tao, Yi Yang, Shengyu Zhang, and
Shuigeng Zhou
Proceedings of the 18th International Conference on Database Theory (ICDT), pages 265-276, 2015.
Nonlocality and conflicting interest games
Anna Pappa, Niraj Kumar, Thomas Lawson, Miklos Santha,
Shengyu Zhang, Eleni Diamanti, Iordanis Kerenidis
Physical Review Letters, 114, 020401, 2015. (Highlighted
in Editors' Suggestion.)
Efficient quantum protocols for XOR functions
Shengyu Zhang
Proceedings of the 25th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1878-1885, 2014.
Earlier at QIP'14. (Slides)
Fourier sparsity, spectral norm, and the Log-rank conjecture
Hing Yin Tsang, Chung Hoi Wong, Ning Xie, Shengyu
Zhang
Proceedings of the 54th Annual IEEE Symposium
on Foundations of Computer Science (FOCS), pages 658-667, 2013. (Slides:
short,
long)
On the
complexity of trial and error
Xiaohui Bei, Ning Chen, Shengyu Zhang
Proceedings of the 45th ACM Symposium on the
Theory of Computing (STOC), pages 31-40, 2013. (Slides)
Quantum and randomized communication complexity of
XOR functions in the SMP model
Yang Liu, Shengyu Zhang
Electronic Colloquium on Computational
Complexity (ECCC), Volume 20, article 10, 2013.
Efficient protocols for generating bipartite
classical distributions and quantum states
Rahul Jain, Yaoyun Shi, Zhaohui Wei, Shengyu Zhang
IEEE Transactions on Information Theory,
Volume 59, Issue 8, pages 5171-5178, Aug 2013.
Earlier at SODA'13. (Slides)
Full characterization of quantum correlated
equilibria
Zhaohui Wei, Shengyu Zhang
Quantum Information and Computation,
Vol. 13, No. 9&10, pp. 0846-0860, 2013.
A
quantum protocol for sampling correlated equilibria unconditionally and
without a mediator
Iordanis Kerenidis, Shengyu Zhang
Proceedings of the 7th Conference on
Theory of Quantum Computation, Communication and Cryptography (TQC),
pages 13-28, 2012. (Slides)
Experimental demonstration of quantum gain in a
zero-sum game
Chong Zu, Yuexuan Wang, Xiuying Chang, Zhaohui
Wei, Shengyu Zhang, Luming Duan
New Journal of Physics, Volume 14, 033002, 2012. (Selected for inclusion in
IOP
Select)
Quantum strategic game theory
Shengyu Zhang
Proceedings of the 3rd Innovations in
Theoretical Computer Science (ITCS), pages 39-59, 2012.
Earlier at QIP'11. (Slides)
On the power of a unique quantum witness
Rahul Jain, Iordanis Kerenidis, Greg Kuperberg,
Miklos Santha, Or Sattath, Shengyu Zhang
Theory of Computing , Volume 8, Article
17, pages 375-400, 2012.
Earlier at QIP'10 and ICS'10. (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), pages 49-60,
2011. (Slides)
The influence lower bound via query elimination
Rahul Jain, Shengyu Zhang
Theory of Computing, Volume 7, pages
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.
Composition theorems in communication complexity
Troy Lee, Shengyu Zhang
Proceedings of the 37th International
Colloquium on Automata, Languages and Programming (ICALP), pages
475-489, 2010.
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), pages 54-59, 2010.
A Survey of BQP-Completeness
Shengyu Zhang
Invited book chapter in
Handbook of Natural Computing, Springer-Verlag, 2010.
Any AND-OR formula of size N can be evaluated in
time N^{1/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), pages 2513-2530, 2010.
Earlier at 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 at STOC'06.
On the tightness of the Buhrman-Cleve-Wigderson
simulation
Shengyu Zhang
Proceedings of the 20th International
Symposium on Algorithms and Computation (ISAAC), pages 434-440, 2009.
(Slides)
Note on quantum counting classes
Yaoyun Shi, Shengyu Zhang
Manuscript 2009.
(The same result was later obtained by Brielin
Brown, Steven T. Flammia, and Norbert Schuch, and published in Physical
Review Letters, 107, 040501, 2011.)
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), pages 318-326, 2009.
New bounds on classical and quantum one-way
communication complexity
Rahul Jain, Shengyu Zhang
Theoretical Computer Science , 410 (26),
pages 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), pages
592-603, 2008.
(Best paper award
of track C.)
Earlier at QIP'07.
How many rounds can Random Selection handle to
obtain general zero-knowledge protocols?
Shengyu Zhang
Information Processing Letters, accepted,
2008.
A single-shot measurement of the energy of product
states in a translation invariant spin chain can replace any quantum
computation
Dominik Janzing, Pawel Wocjan, Shengyu Zhang
New Journal of Physics, (10) 093004,
2008.
Several natural BQP-complete problems
Pawel Wocjan, Shengyu Zhang
quant-ph/0606179, 2006. Superseded by the
above paper with Janzing and Wocjan.
Distributed rate allocation for inelastic flows
Prashanth Hande, Shengyu Zhang, Mung Chiang
IEEE/ACM Transactions on Networking, vol.
15, no. 6, pages 1240-1253, December 2007.
Streaming algorithms measured in terms of the
computed quantity
Shengyu Zhang
Proceedings of the 13th International
Computing and Combinatorics Conference (COCOON), pages 338-348, 2007.
The communication complexity of the Hamming
Distance problem
Wei Huang, Yaoyun Shi, Shengyu Zhang, Yufan Zhu
Information Processing Letters, 99(4),
pages 149-153, 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), pages 430-439, 2005.
On the power of Ambainis lower bounds
Shengyu Zhang
Theoretical Computer Science, 339(2-3),
pages 241-256, 2005.
Earlier at ICALP'04 and invited to TCS.
Graph properties and circular functions: how low
can quantum query complexity go?
Xiaoming Sun, Andrew Yao, Shengyu Zhang
Proceedings of the 19th Annual IEEE Conference
on Computational Complexity (CCC), pages 286-293, 2004.
On the average sensitivity of monotone Boolean
functions
Shengyu Zhang
Manuscript, 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), pages 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.
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,
pages 656-661, 2001.