The MSRA Theory Group aims at advancing the understanding to the foundation of computer science as well as its intersection with other disciplines such as game theory, economics, and social networks. We are collaborating with other researchers and engineers to solve challenging algorithmic and analytical problems in both theory and practice. Currently, our areas of research include computational aspects of social and information networks, algorithmic game theory and mechanism design, algorithm and complexity theory, theory of distributed computing, and computational geometry.
News and Events
- KDD 2012 Tutorial: Infomation and influence spread in social networks, Carlos Castillo, Wei Chen and Laks V. S. Laksshamanan. Aug. 12, 2012
- TKDD CASIN special issue: ACM Transactions on Knowledge Discovery from Data special issue on Computational Aspects of Social and Information Networks. Guest editors: Wei Chen and Jie Tang.
- CASIN'2011: International Workshop on Computational Aspects of Social and Information Networks, July 20-22, 2011. Coorganized by MSRA and Tsinghua University.
- Monthly TCS Seminar at Yangtze Area
- Theory Seminar
- MSRA Theory Workshop, April 2008
Visitors and Collaborators
- 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
- 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]
- 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]
- 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]
- 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]
- 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]
- 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]
- 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]
- 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]
- 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]
- 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]
- 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]
- 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]
- 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]
- 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]
- 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]
- 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]
- 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
- 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]
- Tengyu Ma, Bo Tang, and Yajun Wang, The Simulated Greedy Algorithm for Several Submodular Matroid Secretary Problems, STACS 2013. [arXive:1107.2188]
- Sungjin Im and Yajun Wang. Secretary Problem: Laminar Matroid and Interval Scheduling. SODA 2011. [pdf]
Algorithmic Game Theory and Mechanism Design
- Wei Chen, Yajun Wang, Dongxiao Yu, and Li Zhang. Sybil-proof Mechanisms in Query Incentive Networks. EC 2013. [arxiv:1304.7432]
- Xiaohui Bei, Ning Chen, Nick Gravin and Pinyan Lu: Budget Feasible Mechanism Design: From Prior-Free to Bayesian. STOC 2012. [arXiv]
- Ning Chen, Pinyan Lu, Hongyang Zhang: Computing the Nucleolus of Matching, Cover and Clique Games. AAAI 2012.
- Xue Chen, Guangda Hu, Pinyan Lu and Lei Wang: On the Approximation Ratio of k-lookahead Auction. WINE 2011.
- Ning Chen, Nick Gravin and Pinyan Lu. On the Approximability of Budget Feasible Mechanisms. SODA 2011. [full version]
- Sungjin Im, Pinyan Lu and Yajun Wang. Envy-free Pricing with General Supply Constraints (short paper). WINE 2010
- 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]
- Pinyan Lu, Yajun Wang and Yuan Zhou. Tighter Bounds for Facility Games. WINE 2009.
- Pinyan Lu. On 2-Player Randomized Mechanisms for Scheduling. WINE 2009.
- 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]
Complexity of Counting
- Sangxia Huang, Pinyan Lu: A Dichotomy for Real Weighted Holant Problems. CCC 2012.
- Liang Li, Pinyan Lu, Yitong Yin: Approximate counting via correlation decay in spin systems. SODA 2012: 922-940.
- Heng Guo, Pinyan Lu and Leslie Valiant. The Complexity of Symmetric Boolean Parity Holant Problems. ICALP 2011.
- Jin-Yi Cai, Xi Chen, and Pinyan Lu. Non-negatively Weighted #CSPs: An Effective Complexity Dichotomy. CCC 2011.
- Jin-Yi Cai, Pinyan Lu. Holographic algorithms: From art to science. J. Comput. Syst. Sci. 77(1): 41-61 (2011).
- Heng Guo, Sangxia Huang, Pinyan Lu and Mingji Xia. The Complexity of Weighted Boolean #CSP Modulo k. STACS 2011.
- Jin-Yi Cai, Pinyan Lu and Mingji Xia. Dichotomy for Holant∗ Problems of Boolean Domain. SODA 2011.
- Jin-Yi Cai, Sangxia Huang and Pinyan Lu. From Holant To #CSP And Back: Dichotomy For Holantc Problems. ISAAC 2010. Best paper award.
- Jin-Yi Cai, Pinyan Lu and Mingji Xia. Holographic Algorithms with Matchgates Capture Precisely Tractable Planar #CSP. In Proceedings of FOCS 2010.
- Jin-Yi Cai, Xi Chen, and Pinyan Lu. Graph Homomorphisms with Complex Values: A Dichotomy Theorem. In Proceedings of ICALP 2010. [full version]
- 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]
- 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.
- 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.
- 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]
- 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]
- 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.
- 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]
- 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]
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]
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]
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]
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]
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).
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
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
- 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]
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.
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 firstname.lastname@example.org.