Research Statement of Ke Yang

I am mostly interested in theoretical computer science, including cryptography and security, quantum information theory and quantum computation, machine learning and computational complexity.

Cryptography and Security

Philip MacKenzie , Mike Reiter and Ke Yang,
Alternatives to Non-Malleability: Definitions, Constructions and Applications.
To appear in Theory of Cryptography Conference (TCC '04), Cambridge, MA, 2004.


Juan Garay , Philip MacKenzie and Ke Yang,
Efficient and Universally Composable Committed Oblivious Transfer and Applications.
To appear in Theory of Cryptography Conference (TCC '04), Cambridge, MA, 2004.


Juan Garay , Philip MacKenzie and Ke Yang,
Strengthening Zero-Knowledge Protocols using Signatures.
Appeared in Eurocrypt 2003, Warsaw, Poland, LNCS 2656, pp.177-194, 2003.
[PS] [PDF] [gzipped PS] [ePrint Report 2003/037]

Boaz Barak , Oded Goldreich , Russell Impagliazzo , Steven Rudich , Amit Sahai , Salil Vadhan , and Ke Yang,
On the (Im)possibilities of Obfuscating Pograms.
Appeared in CRYPTO 2001, Santa Baraba, CA, LNCS 2139, pp. 1-18, 2001.
[PS] [PDF] [gzipped PS] [ ECCC TR01-057 ] [ ePrint Report 2001/069 ] [Slides (PS)] [Slides (PDF)] [Slides (gzipped PS)]

Liansheng Huang, Xinbing Wang, Feng Xie and Ke Yang,
Formal Authentication Based on Intruder's Role Impersonate (in Chinese).
Appeared in the Journal of Tsinghua University, July, 2001.

Quantum Information Theoy and Quantum Computation

Avrim Blum and Ke Yang,
On Statistical Query Sampling and NMR Quantum Computing.
Appeared in 18th Aunnual IEEE Conference of Computational Complexity (CCC 2003), Århus, Denmark, pp. 194-205, 2003.
[PS] [PDF] [gzipped PS] [ECCC TR03-014] [quant-ph/0307071]

Andris Ambainis and Ke Yang,
Towards the Classical Communication Complexity of Entanglement Distillation Protocols with Incomplete Information.
[quant-ph/0207090]

Andris Ambainis , Adam Smith and Ke Yang,
Extracting Quantum Entanglement (General Entanglement Purification Protocols).
Appeared in the IEEE Conference of Computational Complexity, Montreal, Quebec, Canada (CCC 2002), pp. 103-112, 2002.
[PS] [PDF] [gzipped PS] [quant-ph/0110011] [IEEE]

Machine Learning

Ke Yang,
New Lower Bounds for Statistical Query Learning.
Appeared in the Fifteenth Annual Conference on Computational Learning Theory, Sydney, NSW, Australia (COLT 2002), LNAI 2375, pp. 229-243, 2002.
Journal version to appear in JCSS.
[PS] [PDF] [gzipped PS] [LNAI 2375] [ECCC TR02-060]

Ke Yang,
On Learning Correlated Functions Using Statistical Query.
Appeared in The Twelfth International Conference on Algorithmic Learning Theory, Washington, DC. (ALT 2001), LNAI 2225, pp. 59-76, 2001.
Journal version to appear in Theoretical Computer Science.
[PS] [PDF] [gzipped PS] [] LNAI 2225 ] [ ECCC TR01-098 ]

Computational Complexity

Manuel Blum , Rachel Rue, and Ke Yang,
On the Complexity of MAX/MIN/AVRG circuits.
CMU SCS Technical Report, CMU-CS-02-110.
[PS] [PDF] [gzipped PS] [ CMU-CS-02-110 ]

Ke Yang,
Integer Circuit Evaluation is PSPACE-complete.
Appeared in the IEEE Conference of Computational Complexity, Florence, Italy, 2000 (CCC 2000) pp. 204 - 213.
Journal version at Journal of Computer and System Sciences, 63, 288-303 (2001).
[PS] [PDF] [gzipped PS] [ ECCC TR00-012 ]

Ke Yang, Xingliang Lin, and Yiqi Dai
Minimal Size of (2,n) Data Sharing Scheme Under XOR Operation (in Chinese).
Appeared in the Journal of Tsinghua University, May, 1998.