基本信息
孙晓明  男  博导  中国科学院计算技术研究所
电子邮件: sunxiaoming@ict.ac.cn
通信地址: 中国科学院计算技术研究所
邮政编码: 100190

研究领域

算法和计算复杂性、量子计算

招生信息

课题组主页:http://theory.ict.ac.cn/en/

招生专业
081202-计算机软件与理论
招生方向
博弈论与社会网络,近似算法,量子计算,通信复杂性
判定树复杂性

教育背景

   
学位
• 清华大学,计算机博士,2005
• 清华大学,计算机学士,2001 

工作经历

• 助理研究员,清华大学高等研究院, 2005.8-2008.12.
• 副研究员,清华大学高等研究院,2008.12-2011.9.
• 研究员,中国科学院计算技术研究所,2011.9-至今.

教授课程

高级算法设计

专利与奖励

2013年获中国密码学会优秀青年奖,2012年获首批国家自然科学基金优秀青年基金资助,入选中组部首批青年拔尖人才支持计划。之前还曾获清华大学“学术新人奖”、“青年教师教学优秀奖”、清华大学优秀博士论文一等奖、微软学者等荣誉。

科研活动

• “数据流模型与判定树模型中的几个问题研究”,国家自然科学基金面上项目,项目负责人,经费57万,2012.1-2015.12

• “理论计算机科学”,国家自然科学基金优秀青年科学基金项目,项目负责人,经费100万,2013.1-2015.12

指导学生

现指导学生

张佳  硕士研究生  081202-计算机软件与理论  

李乾  博士研究生  081202-计算机软件与理论  

出版信息

• Raghav Kulkarni, Youming Qiao, Xiaoming Sun. Any Monotone Property of 3-Uniform Hypergraphs Is Weakly Evasive. Proceedings of 10th International Conference on Theory and Applications of Models of Computation (TAMC), pp. 224-235, Hong Kong, May 2013.

• Yihan Gao, Jieming Mao, Xiaoming Sun, and Song Zuo. On the sensitivity complexity of bipartite graph properties, Theoretical Computer Science 468(14): 83-91 (2013).

• Joshua Brody, Shiteng Chen, Periklis A. Papakonstantinou, Hao Song, and Xiaoming Sun. Space-bounded communication complexity. Proceedings of 4th Innovations in Theoretical Computer Science (ITCS), pp. 159-172, Berkeley, CA, Jan. 2013.

• Yvo Desmedt, Josef Pieprzyk, Ron Steinfeld, Xiaoming Sun, Christophe Tartary, Huaxiong Wang, and Andrew Chi-Chih Yao. Graph Coloring Applied to Secure Computation in Non-Abelian Groups, Journal of Cryptology 25(4): 557-600 (2012).

• John Steinberger, Xiaoming Sun, and Zhe Yang. Stam's Conjecture and Threshold Phenomena in Collision Resistance. Proceedings of 32nd International Cryptology Conference (CRYPTO), pp. 384-405, Santa Barbara, CA, USA, Aug. 2012.

• Magnús Halldórsson, Xiaoming Sun, Mario Szegedy, and Chengu Wang. Streaming and Communication Complexity of Clique Approximation. Proceedings of 39th International Colloquium on Automata, Languages and Programming (ICALP), pp. 449-460, Warwick, UK, Jul. 2012.

• Xiaoming Sun, Chengu Wang, and Wei Yu. The Relationship between Inner Product and Counting Cycles. Proceedings of 10th Latin American Theoretical Informatics Symposium (LATIN), pp. 643-654, Arequipa, Peru, Apr. 2012.

• Joshua Brody, Hongyu Liang, and Xiaoming Sun. Space-Efficient Approximation Scheme for Circular Earth Mover Distance. Proceedings of 10th Latin American Theoretical Informatics Symposium (LATIN), pp. 97-108, Arequipa, Peru, Apr. 2012.

• Xiaoming Sun and Chengu Wang. Randomized Communication Complexity for Linear Algebra Problems over Finite Fields. Proceedings of 29th International Symposium on Theoretical Aspects of Computer Science (STACS), pp. 477-488, Paris, France, Feb. 2012.

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

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

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

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

• Xue Chen, Guangda Hu, and Xiaoming Sun. On the Complexity of Word Circuits. 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.

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

• Xi Chen, Xioaming Sun, and Sheng-Hua Teng. Quantum Separation of Local Search and Fixed Point Computation. 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.

• Bin Ma and Xiaoming Sun. More Efficient Algorithms for Closest String and Substring Problems. 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.

• Xiaoming Sun and Andrew Chi-Chih Yao. On the Quantum Query Complexity of Local Search in Two and Three Dimensions. 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.

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

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

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

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

• Xiaoming Sun. Block Sensitivity of Weakly Symmetric Functions. 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.

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

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

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

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

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

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

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

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

• Yuan Feng, Shengyu Zhang, Xiaoming Sun, and Mingsheng Ying. Universal and Original-Preserving Quantum Copying is Impossible. Physics Letters A 297(1-2): 1-3 (2002).

• Xiaoming Sun, Shengyu Zhang, Yuan Feng, and Mingsheng Ying. Mathematical Nature of and a Family of Lower Bounds for the Success Probability of Unambiguous Discrimination. Physical Review A 65(4): 044306 (2002).

• Shengyu Zhang, Yuan Feng, Xiaoming Sun, and Mingsheng Ying. Upper Bound for the Success Probability of Unambiguous Discrimination among Quantum States. Physical Review A 64(6): 062103 (2001).