
Xiaoming Sun
Room 1250, Institute of Computing Technology, CAS
No.6 Kexueyuan South Road, Zhongguancun
Haidian District, Beijing 100190, China
Email: sunxiaoming@ict.ac.cn

Education
 Tsinghua University, Beijing, China. PhD in Computer Science, 2005
 Tsinghua University, Beijing, China. BS in Computer Science, 2001
Employment
 Assistant Professor, Institute for Advanced Study, Tsinghua University, 2005.82008.12.
 Associate Professor, Institute for Advanced Study, Tsinghua University, 2008.122011.9.
 Professor, Institute of Computing Technology, China Academy of Sciences, 2011.9present.
Professional Service
 Subject Area Editor of Journal of Computer Science and Technology
 Program Committee. The 16th/20th/23rd International Symposium on Algorithms and Computation (ISAAC 2005/2009/2012)
 Program Committee. The 4th/5th/7th/9th Annual Conference on Theory and Applications of Models of Computation (TAMC 2007/2008/2010/2012)
 Program Committee. The 16th Computing: The Australasian Theory Symposium (CATS 2010)
 Program Committee. The 33rd/34th/35th Australasian Computer Science Conference (ACSC 2010/2011/2012)
 Program Committee. The 3rd Annual Meeting of the Asian Association for Algorithms and Computation (AAAC 2010)
 Program Committee. The 5th Annual International Conference on Combinatorial Optimization and Applications (COCOA 2011)
 Program Committee. The 18th Annual International Computing and Combinatorics Conference (COCOON 2012)
 Program Committee. The 6th International Frontiers of Algorithmics Workshop (FAW 2012)
 Program Committee. The 8th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2013)
Publications
 Raghav Kulkarni, Youming Qiao, Xiaoming Sun. Any Monotone Property of 3Uniform Hypergraphs Is Weakly Evasive. Proceedings of 10th International Conference on Theory and Applications of Models of Computation (TAMC), pp. 224235, 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): 8391 (2013).
 Joshua Brody, Shiteng Chen, Periklis A. Papakonstantinou, Hao Song, and Xiaoming Sun. Spacebounded communication complexity. Proceedings of 4th Innovations in Theoretical Computer Science (ITCS), pp. 159172, Berkeley, CA, Jan. 2013.
 Yvo Desmedt, Josef Pieprzyk, Ron Steinfeld, Xiaoming Sun, Christophe Tartary, Huaxiong Wang, and Andrew ChiChih Yao. Graph Coloring Applied to Secure Computation in NonAbelian Groups, Journal of Cryptology 25(4): 557600 (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. 384405, 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. 449460, 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. 643654, Arequipa, Peru, Apr. 2012.
 Joshua Brody, Hongyu Liang, and Xiaoming Sun. SpaceEfficient Approximation Scheme for Circular Earth Mover Distance. Proceedings of 10th Latin American Theoretical Informatics Symposium (LATIN), pp. 97108, 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. 477488, 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. 616626, Dallas, TX, USA, Aug. 2011.
 Xiaoming Sun. An Improved Lower Bound on the Sensitivity Complexity of Graph Properties. Theoretical Computer Science 412(29): 35243529 (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. 124132, Tokyo, Japan, May 2011.
 Tiancheng Lou, Xiaoming Sun, and Christophe Tartary. Bounds and tradeoffs for DoubleBase Number Systems. Information Processing Letters 111(10): 488493, (2011).
 Xue Chen, Guangda Hu, and Xiaoming Sun. On the Complexity of Word Circuits. Discrete Mathematics, Algorithms and Application 2(4): 483492, (2010). Earlier version in Proceedings of 16th Annual International Computing and Combinatorics Conference (COCOON), pp. 308317, 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. 6677, Brno, Czech Republic, Aug. 2010.
 Xi Chen, Xioaming Sun, and ShengHua Teng. Quantum Separation of Local Search and Fixed Point Computation. ALGORITHMICA 56(3): 364382 (2010). A preliminary version appeared in Proceedings of 14th Annual International Computing and Combinatorics Conference (COCOON), pp. 170179, Dalian, China, Jun. 2008.
 Bin Ma and Xiaoming Sun. More Efficient Algorithms for Closest String and Substring Problems. SIAM Journal on Computing 39(4): 14321443 (2009). A preliminary version appeared in Proceedings of 12th Annual International Conference on Research in Computational Molecular Biology (RECOMB), 396409, Singapore, Mar. 2008.
 Xiaoming Sun and Andrew ChiChih Yao. On the Quantum Query Complexity of Local Search in Two and Three Dimensions. ALGORITHMICA 55(3): 576600 (2009). Earlier version in Proceedings of 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS), pp. 429438, Berkeley, CA, Oct. 2006.
 Yuchen Zhang and Xiaoming Sun. The Antimagicness of the Cartesian Product of Graphs. Theoretical Computer Science 410(810): 727735 (2009).
 Xiaoming Sun, Andrew ChiChih Yao, and Christophe Tartary. Graph Design for Secure Multiparty Computation over NonAbelian Groups. Proceeding of 14th International Conference on the Theory and Application of Cryptology and Information Security (AsiaCrypt), pp. 3753, Melbourne, Australia, Dec. 2008.
 Tsuyoshi Ito, Hirotada Kobayashi, Daniel Preda, Xiaoming Sun, and Andrew ChiChih Yao. Generalized Tsirelson Inequalities, CommutingOperator Provers, and MultiProver Interactive Proof Systems. Proceedings of 23rd IEEE Conference on Computational Complexity (CCC), pp. 187198, College Park, MD, Jun. 2008.
 Yongxi Cheng, Xiaoming Sun, and Yiqun Lisa Yin. Searching Monotone Multidimensional Arrays. Discrete Mathematics 308(11): 22132221, (2008).
 Xiaoming Sun. Block Sensitivity of Weakly Symmetric Functions. Theoretical Computer Science 384(1): 8791 (2007). Conference version in Proceedings of Theory and Applications of Models of Computation (TAMC), pp. 339344, Beijing, May 2006.
 Xiaoming Sun and David Woodruff. The Communication and Streaming Complexity of Computing the Longest Common and Increasing Subsequences. Proceedings of 18th ACMSIAM Symposium on Discrete Algorithms (SODA), pp. 336345, 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): 7580 (2005).
 Ning Chen, Xiaotie Deng, and Xiaoming Sun. On Complexity of SingleMinded Auction. Journal of Computer and System Sciences 69(4): 675687 (2004).
 Xiaoming Sun, Andrew ChiChih 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. 286293, Amherst, MA, Jun. 2004.
 Ning Chen, Xiaotie Deng, Xiaoming Sun, and Andrew ChiChih Yao. Fisher Equilibrium Price with a Class of Concave Utility Functions. Proceedings of 12th Annual European Symposium on Algorithms (ESA), pp. 169179, Bergen, Norway, Sep. 2004.
 Ning Chen, Xiaotie Deng, Xiaoming Sun, and Andrew ChiChih Yao. Dynamic Price Sequence and Incentive Compatibility. Proceedings of 31st International Colloquium on Automata, Languages and Programming (ICALP), pp. 320331, 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: 399408 (2004).
 Xiaoming Sun. A 3Party simultaneous Protocol for SUMINDEX. ALGORITHMICA 36(1): 8991 (2003).
 Yuan Feng, Shengyu Zhang, Xiaoming Sun, and Mingsheng Ying. Universal and OriginalPreserving Quantum Copying is Impossible. Physics Letters A 297(12): 13 (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).
