基本信息
孙晓明男博导中国科学院计算技术研究所
电子邮件： 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).