当前位置 >>  首页 >> 研究队伍 >> 研究员

孙晓明

撰稿: 摄影: 发布时间:2012年05月01日

P020111012370068961385.jpg

科研人员
性别   男
职称   研究员
所属部门   前瞻研究实验室
研究方向

 量子计算,通信复杂性,判定树复杂性,近似算法,组合数学

个人主页   http://www.carch.ac.cn/~xmsun  
简历

1997年9月-2001年7月:清华大学计算机系,学士毕业 
2001年9月-2005年7月:清华大学计算机系,博士毕业 
2005年8月-2008年12月:清华大学高等研究院,助理研究员 
2008年12月-2011年9月:清华大学高等研究院,副研究员 
2011年9月至今:中国科学院计算技术研究所

社会任职

Journal of Computer Science and Technology杂志编委,Math Reviews评论员,ISAAC, COCOON, TAMC, AAAC, CATS, COCOA, ACSC等国际会议程序委员会委员,STOC, SODA, CCC, ICALP, Eurocrypt等国际会议和JCSS, Algorithmica, IPL, TCS等期刊审稿人。

获奖及荣誉

曾获微软学者,清华大学优秀毕业生,清华大学优秀博士论文一等奖,入选清华大学基础学科青年人才支持计划,清华大学学术新人奖,清华大学青年教师教学优秀奖等荣誉。

 

 

 

 

 

 

 

 

 

 

 

代表论著

1.A New Variation of Hat Guessing Games. Tengyu Ma, Xiaoming Sun, and Huacheng Yu, 17th Annual International Computing and Combinatorics Conference (COCOON), pp. 616-626, Dallas, TX, USA, Aug. 2011.

2.An Improved Lower Bound on the Sensitivity Complexity of Graph Properties. Xiaoming Sun. Theoretical Computer Science 412(29): 3524-3529 (2011).

3.A Better Upper Bound on Weights of Exact Threshold Functions. Xue Chen, Guangda Hu, and Xiaoming Sun. 8th International Conference on Theory and Applications of Models of Computation (TAMC), pp. 124-132, Tokyo, Japan, May 2011.

4.Bounds and trade-offs for Double-Base Number Systems. Tiancheng Lou, Xiaoming Sun, and Christophe Tartary. Information Processing Letters 111(10): 488-493, (2011).

5.On the Complexity of Word Circuits. Xue Chen, Guangda Hu, and Xiaoming Sun. Discrete Mathematics, Algorithms and Application 2(4): 483-492, (2010). Earlier version in Proceedings of 16th Annual International Computing and Combinatorics Conference (COCOON), pp. 308-317, Nha Trang, Vietnam, Jul. 2010.

6.Weights of Exact Threshold Functions. Laszlo Babai, Kristoffer Hansen, Vladimir Podolskii, and Xiaoming Sun. Proceedings of 35th International Symposium on Mathematical Foundations of Computer Science (MFCS), pp. 66-77, Brno, Czech Republic, Aug. 2010.

7.Quantum Separation of Local Search and Fixed Point Computation. Xi Chen, Xioaming Sun, and Sheng-Hua Teng. ALGORITHMICA 56(3): 364-382 (2010). A preliminary version appeared in Proceedings of 14th Annual International Computing and Combinatorics Conference (COCOON), pp. 170-179, Dalian, China, Jun. 2008.

8.More Efficient Algorithms for Closest String and Substring Problems. Bin Ma and Xiaoming Sun. SIAM Journal on Computing 39(4): 1432-1443 (2009). A preliminary version appeared in Proceedings of 12th Annual International Conference on Research in Computational Molecular Biology (RECOMB), 396-409, Singapore, Mar. 2008.

9.On the Quantum Query Complexity of Local Search in Two and Three Dimensions. Xiaoming Sun and Andrew Chi-Chih Yao. ALGORITHMICA 55(3): 576-600 (2009). Earlier version in Proceedings of 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS), pp. 429-438, Berkeley, CA, Oct. 2006.

10.The Antimagicness of the Cartesian Product of Graphs. Yuchen Zhang and Xiaoming Sun. Theoretical Computer Science 410(8-10): 727-735 (2009).

11.Graph Design for Secure Multiparty Computation over Non-Abelian Groups. Xiaoming Sun, Andrew Chi-Chih Yao, and Christophe Tartary. Proceeding of 14th International Conference on the Theory and Application of Cryptology and Information Security (AsiaCrypt), pp. 37-53, Melbourne, Australia, Dec. 2008.

12.Generalized Tsirelson Inequalities, Commuting-Operator Provers, and Multi-Prover Interactive Proof Systems. Tsuyoshi Ito, Hirotada Kobayashi, Daniel Preda, Xiaoming Sun, and Andrew Chi-Chih Yao. Proceedings of 23rd IEEE Conference on Computational Complexity (CCC), pp. 187-198, College Park, MD, Jun. 2008.

13.Searching Monotone Multi-dimensional Arrays. Yongxi Cheng, Xiaoming Sun, and Yiqun Lisa Yin. Discrete Mathematics 308(11): 2213-2221, (2008).

14.Block Sensitivity of Weakly Symmetric Functions. Xiaoming Sun. Theoretical Computer Science 384(1): 87-91 (2007). Conference version in Proceedings of Theory and Applications of Models of Computation (TAMC), pp. 339-344, Beijing, May 2006.

15.The Communication and Streaming Complexity of Computing the Longest Common and Increasing Subsequences. Xiaoming Sun and David Woodruff. Proceedings of 18th ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 336-345, New Orleans, LA, Jan. 2007.

16.The Existence of Quantum Entanglement Catalysts. Xiaoming Sun, Runyao Duan and Mingsheng Ying. IEEE Transactions on Information Theory 50(1): 75-80 (2005).

17.On Complexity of Single-Minded Auction. Ning Chen, Xiaotie Deng, and Xiaoming Sun. Journal of Computer and System Sciences 69(4): 675-687 (2004).

18.Graph Properties and Circular Functions: How Low Can Quantum Query Complexity Go? Xiaoming Sun, Andrew Chi-Chih Yao, and Shengyu Zhang. Proceedings of 19th IEEE Conference on Computational Complexity (CCC), pp. 286-293, Amherst, MA, Jun. 2004.

19.Fisher Equilibrium Price with a Class of Concave Utility Functions. Ning Chen, Xiaotie Deng, Xiaoming Sun, and Andrew Chi-Chih Yao. Proceedings of 12th Annual European Symposium on Algorithms (ESA), pp. 169-179, Bergen, Norway, Sep. 2004.

20.Dynamic Price Sequence and Incentive Compatibility. Ning Chen, Xiaotie Deng, Xiaoming Sun, and Andrew Chi-Chih Yao. Proceedings of 31st International Colloquium on Automata, Languages and Programming (ICALP), pp. 320-331, Turku, Finland, Jul. 2004.

21.Performance Evaluation for Energy Efficient Topological Control in Ad Hoc Wireless Networks. Minming Li, S. Huang, Xiaoming Sun, and Xiao Huang. Theoretical Computer Science 326: 399-408 (2004).

22.A 3-Party simultaneous Protocol for SUM-INDEX. Xiaoming Sun. ALGORITHMICA 36(1): 89-91 (2003).

23.Universal and original-preserving quantum copying is impossible. Yuan Feng, Shengyu Zhang, Xiaoming Sun, and Mingsheng Ying. Physics Letters A 297(1-2): 1-3 (2002).

24.Mathematical nature of and a family of lower bounds for the success probability of unambiguous discrimination. Xiaoming Sun, Shengyu Zhang, Yuan Feng, and Mingsheng Ying. Physical Review A 65(4): 044306 (2002).

25.Upper bound for the success probability of unambiguous discrimination among quantum states. Shengyu Zhang, Yuan Feng, Xiaoming Sun, and Mingsheng Ying. Physical Review A 64(6): 062103 (2001).
 

承担科研项目情况

1.“量子计算复杂性与经典计算复杂性的关系”,国家自然科学基金青年基金,项目负责人 
2.“智能信息处理的理论和方法”,国家自然科学基金创新群体项目,项目骨干 
3.“安全计算学重大理论问题研究”,973项目,项目骨干 
4.“数据流模型与判定树模型中的几个问题研究”,国家自然科学基金面上项目,项目负责人

学科类别 计算机软件与理论
专家类别 正高
附件下载: