Theory Group

Overview

MSRA Theory Group aims at advancing the foundation of computer science and its intersection with other disciplines such as game theory, economics, social networks, optimization and statistical physics. We collaborate with other researchers and engineers to solve challenging algorithmic and analytical problems in both theory and practice. Currently, our research areas include computational aspects of social and information networks, algorithmic game theory, mechanism design, online learning, algorithm and complexity, and distributed computing.

News and Events

Visitors and Collaborators

  • Dr. Zhi Yang, Peking University
  • Prof. Xiaotie Deng, Shanghai Jiao Tong University
  • Dr. Yitong Yin, Nanjing University, China
  • Dr. Michael Mahoney, Stanford University, USA
  • Prof. Bin Yu, University of California at Berkeley, USA
  • Dr. David Xiao, Universite Paris-Sud, France
  • Dr. Ning Chen, Nanyang Technological University, Singapore
  • Dr. Peng Zhang, Shandong University, China
  • Prof. Jin-Yi Cai, University of Wisconsin at Madison, USA
  • Dr. Li Zhang, Microsoft Research Silicon Valley, USA
  • Prof. Shang-Hua Teng, University of Southern California, USA
  • Prof. John Hopcroft, Cornell University, USA
  • Prof. Yanhong Annie Liu, State University of New York at Stony Brook, USA
  • Dr. Heiko Roglin, Post-doc of Boston University, USA
  • Dr. Cynthia Dwork, Microsoft Research Silicon Valley, USA
  • Dr. Xiangyang Li, Illinois Institute of Technology, USA
  • Prof. Jeong Han Kim, Yonsei University, Korea

Research Areas with Recent Publications

Social and Information Networks

  1. Wei Chen, Laks V.S. Lakshmanan, and Carlos Castillo. Information and Influence Propagation in Social Networks. Morgan & Claypool, 2013. [Morgan & Claypool official book page]
  2. Wei Chen, Guangda Hu, Wenjie Fang, and Michael W. Mahoney. On the hyperbolicity of small-world and tree-like random graphs. Internet Mathematics 9 (4), 2013, pp 434 - 491. [pdf]
  3. Sejeong Kwon, Meeyoung Cha, Kyomin Jung, Wei Chen, and Yajun Wang. Prominent features of rumor propagation in online social media. In Proceedings of the 13th IEEE International Conference on Data Mining (ICDM'2013), Dallas, Texas, U.S.A., Dec. 2013. [pdf]
  4. De-Nian Yang, Hui-Ju Hung, Wang-Chien Lee, and Wei Chen. Maximizing acceptance probability for active friending in online social networks. In Proceedings of 19th ACM SIGKDD Conference on Knowledge Discovery and Data Mining (KDD'2013), Chicago, Illinois, U.S.A., August, 2013. [pdf][full technical report: arXiv: 1302.7025]
  5. Wei Chen, Yajun Wang, Dongxiao Yu, and Li Zhang. Sybil-proof mechanisms in query incentive networks. In Proceedings of 14th ACM Conference on Electronic Commerce (EC'2013), Philadelphia, Pennsylvania, U.S.A., June 2013. [pdf with typos fixed] [full technical report: arXiv:1304.7432]
  6. Yanhua Li, Wei Chen, Yajun Wang, and Zhi-Li Zhang. Influence diffusion dynamics and influence maximization in social networks with friend and foe relationships. In Proceedings of the 6th International Conference on Web Search and Data Mining (WSDM'13), Rome, Italy, Feb. 2013. [pdf][full technical report: arXiv:1111.4729]
  7. Wei Chen, Wenjie Fang, Guangda Hu, and Michael Mahoney. On the Hyperbolicity of Small-World and Tree-Like Random Graphs. In Proceedings of The 23rd International Symposium on Algorithms and Computation (ISAAC'2012), Taipei, Taiwan, December 2012. [pdf][full technical report: arXiv:1201.1717]
  8. Chi Wang, Wei Chen, and Yajun Wang. Scalable influence maximization for independent cascade model in large-scale social networks. Data Mining and Knowledge Discovery Journal, 25(3), 2012, pp. 545 - 576. [pdf]
  9. Wei Chen, Wei Lu, and Ning Zhang. Time-critical influence maximization in social networks with time-delayed diffusion process. In Proceedings of the 26th Conference on Artificial Intelligence (AAAI'2012), Toronto, Canada, July 2012. [pdf] [full technical report: arXiv:1204.3074]
  10. Xinran He, Guojie Song, Wei Chen, and Qingye Jiang. Influence blocking maximization in social networks under the competitive linear threshold model. In Proceedings of the 12th SIAM International Conference on Data Mining (SDM'2012), Anaheim, CA, U.S.A., April, 2012. [pdf] [full technical report: arXiv:1110.4723]
  11. Wei Chen, Pinyan Lu, Xiaorui Sun, Bo Tang, Yajun Wang, and Zeyuan Allen Zhu. Optimal pricing in social networks with incomplete information. In Proceedings of the 7th Workshop on Internet and Network Economics (WINE'2011), Singapore, December 2011. [pdf][full technical report: arXiv:1007.1501]
  12. Tao Sun, Wei Chen, Zhenming Liu, Yajun Wang, Xiaorui Sun, Ming Zhang, and Chin-Yew Lin. Participation maximization based on social influence in online discussion forums. In Proceedings of the 5th International AAAI Conference on Weblogs and Social Media (ICWSM'2011), Barcelona, Spain, July 2011. [pdf][full technical report: MSR-TR-2010-142]
  13. Wei Chen, Alex Collins, Rachel Cummings, Te Ke, Zhenming Liu, David Rincon, Xiaorui Sun, Yajun Wang, Wei Wei, and Yifei Yuan. Influence maximization in social networks when negative opinions may emerge and propagate. In Proceedings of the 11th SIAM International Conference on Data Mining (SDM'2011), Phoenix, U.S.A., April, 2011. [pdf][full technical report: MSR-TR-2010-137]
  14. Shaojie Tang, Jing Yuan, Xufei Mao, Xiang-Yang Li, Wei Chen, and Guojun Dai. Relationship Classification in Large Scale OSN and its impact on information propagation. In Proceedings of the 30th IEEE International Conference on Computer Communications (INFOCOM'2011), Shanghai, China, April, 2011. [pdf]
  15. Wei Chen, Yifei Yuan, and Li Zhang. Scalable influence maximization in social networks under the linear threshold model. In Proceedings of the 10th IEEE International Conference on Data Mining (ICDM'2010), Sydney, Australia, Dec. 2010. [pdf][full technical report: MSR-TR-2010-133]
  16. Wei Chen, Zhenming Liu, Xiaorui Sun, and Yajun Wang. A game-theoretic framework to identify overlapping communities in social networks. Data Mining and Knowledge Discovery Journal, special issue on ECML PKDD 2010, 21(2), September, 2010, 224-240. Winner of the best student paper award in data mining at ECML PKDD 2010. [pdf]
  17. Wei Chen, Chi Wang, and Yajun Wang. Scalable influence maximization for prevalent viral marketing in large-scale social networks. In Proceedings of the 16th ACM SIGKDD Conference on Knowledge Discovery and Data Mining (KDD'2010), Washinton, DC, USA, July. 2010. [pdf] [full technical report: MSR-TR-2010-2]
  18. Wei Chen, Christian Sommer, Shang-Hua Teng, and Yajun Wang. Compact routing in power-law graphs. In Proceedings of the 23rd International Symposium on Distributed Computing (DISC'2009), Elche/Elx, Spain, Sept. 2009. [pdf] [full technical report: MSR-TR-2009-84]
  19. Xiaohui Bei, Wei Chen, Shang-Hua Teng, Jialin Zhang, and Jiajie Zhu. Bounded budget betweenness centrality game for strategic network formations. In Proceedings of the 17th European Symposium of Algorithms (ESA'2009), Copenhagen, Denmark, Sept. 2009. [pdf] [full technical report: MSR-TR-2009-78][related technical report: MSR-TR-2008-167]
  20. Wei Chen, Yajun Wang, and Siyu Yang. Efficient influence maximization in social networks. In Proceedings of the 15th ACM SIGKDD Conference on Knowledge Discovery and Data Mining (KDD'2009), Paris, France, June 2009. [pdf]
  21. Wei Chen, Shang-Hua Teng, Yajun Wang, and Yuan Zhou. On the $\alpha$-sensitivity of Nash equilibria in PageRank-based network reputation games. In Proceedings of the 3rd International Frontiers of Algorithmics Workshop (FAW'2009), Hefei, China, June 2009. [pdf]
  22. Kazuya Okamoto, Wei Chen, and Xiang-Yang Li. Ranking of closeness centrality for large-scale social networks. In Proceedings of the 2nd International Frontiers of Algorithmics Workshop (FAW'2008), Changsha, China, June 2008. [pdf]

Online Algorithms and Online Learning

  1. Tian Lin, Bruno Abrahao, Robert Kleinberg, John C. S. Lui, and Wei Chen. Combinatorial partial monitoring game with linear feedback and its applications. In Proceedings of the 31st International Conference on Machine Learning (ICML'2014), Beijing, China, June 2014. [pdf] [supplementary material]
  2. Wei Chen, Yajun Wang, and Yang Yuan. Combinatorial multi-armed bandit:
    general framework, results and applications. In Proceedings of the 30th International Conference on Machine Learning (ICML'13), Atlanta, Georgia, U.S.A., June, 2013. [pdf][supplementary material]
  3. Tengyu Ma, Bo Tang, and Yajun Wang, The Simulated Greedy Algorithm for Several Submodular Matroid Secretary Problems, STACS 2013. [arXive:1107.2188]
  4. Sungjin Im and Yajun Wang. Secretary Problem: Laminar Matroid and Interval Scheduling. SODA 2011. [pdf]

Algorithmic Game Theory and Mechanism Design

  1. Ning Chen, Nick Gravin and Pinyan Lu: Optimal Competitive Auctions.  STOC 2014.
  2. Ning Chen, Nick Gravin and Pinyan Lu: Truthful Generalized Assignments via Stable Matching.  Mathematics of Operations Research, 2013.
  3. Pinyan Lu and Lan Yu: Characterization of Truthful Mechanisms for One-dimensional Single Facility Location Game with Payments.  WINE 2013.
  4. Nick Gravin and Pinyan Lu: Competitive Auctions for Markets with Positive Externalities. with Nick Gravin, ICALP 2013.
  5. Wei Chen, Yajun Wang, Dongxiao Yu, and Li Zhang. Sybil-proof Mechanisms in Query Incentive Networks. EC 2013. [arxiv:1304.7432]
  6. Xiaohui Bei, Ning Chen, Nick Gravin and Pinyan Lu: Budget Feasible Mechanism Design: From Prior-Free to Bayesian. STOC 2012. [arXiv]
  7. Ning Chen, Pinyan Lu, Hongyang Zhang: Computing the Nucleolus of Matching, Cover and Clique Games. AAAI 2012.
  8. Xue Chen, Guangda Hu, Pinyan Lu and Lei Wang: On the Approximation Ratio of k-lookahead Auction. WINE 2011.
  9. Ning Chen, Nick Gravin and Pinyan Lu. On the Approximability of Budget Feasible Mechanisms.  SODA 2011. [full version]
  10. Sungjin Im, Pinyan Lu and Yajun Wang. Envy-free Pricing with General Supply Constraints (short paper). WINE 2010
  11. Pinyan Lu, Xiaorui Sun, Yajun Wang, and Zeyuan Allen Zhu. Asymptotically Optimal Strategy-Proof Mechanisms for Two-Facility Games. In Proceedings of the 11th ACM Conference on Electronic Commerce (EC'10) in Cambridge, MA, USA, June 2010. [pdf]
  12. Pinyan Lu, Yajun Wang and Yuan Zhou. Tighter Bounds for Facility Games. WINE 2009.
  13. Pinyan Lu. On 2-Player Randomized Mechanisms for Scheduling.  WINE 2009.
  14. Yingchao Zhao, Wei Chen, and Shang-Hua Teng. The isolation game: A game of distances. Theoretical Computer Science, 410(47-49), 2009, 4905-4919. [pdf]
    An extended abstract appeared in Proceedings of the 19th International Symposium on Algorithms and Computation ( ISAAC'2008), Gold Coast, Australia, Dec. 2008. [pdf]

Approximate Counting

  1. Pinyan Lu, Menghui Wang and Chihao Zhang: FPTAS for Weighted Fibonacci Gates and Its Applications.  ICALP 2014.
  2. Chengyu Lin, Jingcheng Liu and Pinyan Lu: A Simple FPTAS for Counting Edge Covers.  SODA 2014.
  3. Pinyan Lu and Yitong Yin: Improved FPTAS for Multi-Spin Systems. RANDOM 2013.
  4. Xi Chen, Martin Dyer, Leslie Ann Goldberg, Mark Jerrum, Pinyan Lu, Colin McQuillan and David Richerby: The Complexity of Approximating Conservative Counting CSPs. STACS 2013.
  5. Liang Li, Pinyan Lu and Yitong Yin: Correlation Decay up to Uniqueness in Spin Systems. SODA 2013.
  6. Jin-Yi Cai, Xi Chen, Pinyan Lu and Heng Guo: Inapproximability After Uniqueness Phase Transition in Two-Spin Systems.  COCOA 2012.
  7. Liang Li, Pinyan Lu and Yitong Yin: Approximate Counting via Correlation Decay in Spin Systems. SODA 2012.

Complexity of Counting

  1. Jin-Yi Cai, Pinyan Lu and Mingji Xia: Dichotomy for Holant* Problems with a Function on Domain Size 3.  SODA 2013.
  2. Sangxia Huang, Pinyan Lu: A Dichotomy for Real Weighted Holant Problems. CCC 2012.
  3. Heng Guo, Pinyan Lu and Leslie Valiant. The Complexity of Symmetric Boolean Parity Holant Problems. ICALP 2011.
  4. Jin-Yi Cai, Xi Chen, and Pinyan Lu. Non-negatively Weighted #CSPs: An Effective Complexity Dichotomy. CCC 2011.
  5. Jin-Yi Cai, Pinyan Lu. Holographic algorithms: From art to science. J. Comput. Syst. Sci. 77(1): 41-61 (2011).
  6. Heng Guo, Sangxia Huang, Pinyan Lu and Mingji Xia. The Complexity of Weighted Boolean #CSP Modulo k. STACS 2011.
  7. Jin-Yi Cai, Pinyan Lu and Mingji Xia: Dichotomy for Holant Problems of Boolean Domain. SODA 2011.
  8. Jin-Yi Cai, Sangxia Huang and Pinyan Lu.  From Holant To #CSP And Back: Dichotomy For Holantc Problems. ISAAC 2010. Best  paper award.  
  9. Jin-Yi Cai, Pinyan Lu and Mingji Xia. Holographic Algorithms with Matchgates Capture Precisely Tractable Planar #CSP. In Proceedings of FOCS 2010.
  10. Jin-Yi Cai, Xi Chen, and Pinyan Lu. Graph Homomorphisms with Complex Values: A Dichotomy Theorem. In Proceedings of ICALP 2010. [full version]
  11. Jin-Yi Cai, Xi Chen, Richard J. Lipton, and Pinyan Lu. On Tractable Exponential Sums. In Proceedings of FAW 2010. Best Paper Award. [full version]
  12. Jin-Yi Cai, Pinyan Lu and Mingji Xia. Holant Problems and Counting CSP. In Proceedings of the 41st ACM Symposium on Theory of Computing (STOC' 2009), Bethesda, Maryland, USA, May. 2009.
  13. Jin-Yi Cai, Pinyan Lu and Mingji Xia. A Computational Proof of Complexity of Some Restricted Counting Problems. In Proceedings of the 6th Annual Conference on Theory and Applications of Models of Computation (TAMC' 2009), ChangSha, China, May 2009.

Distributed Computing

  1. Wei Chen, Guangda Hu, and Jialin Zhang. On the power of breakable objects. Theoretical Computer Science, 503, Sept. 2013, pp 89 - 108. [pdf]
  2. Yang Liu, Wei Chen, Yanhong A. Liu, Jun Sun, Shao Jie Zhang, and Jin Song Dong. Verifying linearizability via optimized refinement checking. IEEE Transactions on Software Engineering, 39(7), July 2013. [pdf]
  3. Wei Chen, Christian Sommer, Shang-Hua Teng, and Yajun Wang. A compact routing scheme and approximate distance oracle for power-law graphs. ACM Transactions on Algorithms, 9(1), Dec. 2012. [pdf]
  4. Zhi Yang, Jing Tian, Ben Y. Zhao, Wei Chen, and Yafei Dai. Protector: A probabilistic failure detector for cost-effective peer-to-peer storage. IEEE Transactions on Parallel and Distributed Systems. 22(9), September, 2011, pp. 1514 - 1527. [pdf]
  5. Jialin Zhang and Wei Chen. Implementing uniform reliable broadcast with binary consensus in systems with fair-lossy links. Information Processing Letters, Elsevier, (110), 2009, pp. 13 -19. [pdf][full technical report: MSR-TR-2008-162]
  6. Yang Liu, Wei Chen, Yanhong A. Liu, and Jun Sun. Model checking linearizability via refinement. In Proceedings of the 16th International Symposium on Formal Methods (FM'2009), Eindhoven, the Netherlands, Nov. 2009.
  7. Jialin Zhang and Wei Chen. Bounded cost algorithms for multivalued consensus using binary consensus instances. Information Processing Letters, Elsevier, (109), 2009, pp. 1005 -1009. [pdf]
  8. Jing Tian, Zhi Yang, Wei Chen, Ben Y. Zhao and Yafei Dai. Probabilistic failure detection for efficient distributed storage maintenance. In Proceedings of the 27th IEEE International Symposium on Reliable Distributed Systems (SRDS'2008), Napoli, Italy, Oct. 2008. [pdf]
  9. Wei Chen, Jialin Zhang, Yu Chen, and Xuezheng Liu. Failure detectors and extended paxos for k-set agreement. In Proceedings of the 13th IEEE Pacific Rim International Symposium on Dependable Computing (PRDC'2007), Melbourne, Australia, Dec. 2007. [pdf] [technical report: MSR-TR-2007-48]

  10. Yu Chen and Wei Chen. Decentralized, connectivity-preserving, and cost-effective structured overlay maintenance. In Proceedings of the 9th International Symposium on Stabilization, Safety, and Security of Distributed Systems (SSS'2007), Paris, France, Nov. 2007. [pdf] [technical report: MSR-TR-2007-84]

  11. Ming Chen, Wei Chen, and Zheng Zhang. An analytical framework and its applications for studying brick storage reliability. In Proceedings of the 26th IEEE International Symposium on Reliable Distributed Systems (SRDS'2007), Beijing, China, Oct. 2007. [pdf]

  12. Wei Chen, Jialin Zhang, Yu Chen, and Xuezheng Liu. Weakening failure detectors for k-set agreement via the partition approach. In Proceedings of the 21st International Symposium on Distributed Computing (DISC'2007), Lemesos, Cyprus, Sept. 2007. [pdf] [technical reports: MSR-TR-2007-49, MSR-TR-2007-50]

Computational Geometry

  1. Siu-Wing Cheng, Jiongxin Jin, Antoine Vigneron, and Yajun Wang, Approximate Shortest Homotopic Paths in Weighted Regions, in the International Journal of Computational Geometry and Applications (IJCGA) vol 22, no 1, Sep 2012. (special issue of ISAAC 2010).

  2. Tetsuo Asano, Wolfgang Mulzer, Gunter Rote and Yajun Wang, Constant-Work-Space Algorithms for Geometric Problems, in Journal of Computational Geometry 2(1) (JoCG), Jul 2011

  3. Tetsuo Asano, Wolfgang Mulzer and Yajun Wang, Constant-Work-Space Algorithms for Shortest Paths in Trees and Simple Polygons, invited to the special issues of WALCOM in Journal of Graph Algorithms and Applications (JGAA), 2011

  4. Siu-Wing Cheng, Hyeon-Suk Na, Antoine Vigneron, and Yajun Wang, Querying Approximate Shortest Paths in Anisotropic Regions, in SIAM J. COMPUTING, vol. 39, no. 5, pp. 1888-1918, Society for Industrial and Applied Mathematics, 2010. [pdf]
  5. Xiang-Yang Li, Yajun Wang, and Wangsen Feng. Multiple Round Random Ball Placement: Power of Second Chance. In Proceedings of the 15th International Computing and Combinatorics Conference (COCOON'2009), New York, USA, July 2009.

Joining Us

We are welcoming applications to our full-time employee positions and regular internship positions. We are also welcoming visiting researchers from academia and industry to visit our group, for days, weeks, or longer period of time. If you are interested in joining our theory group, please send email to Wei Chen at weic@microsoft.com.