Overview

The MSRA Theory Group aims at advancing the understanding to the foundation of computer science and collaborating with others researchers and engineers to solve challenging algorithmic and analytical problems. Currently, our areas of research include algorithmic game theory, algorithmic aspects of social networks, theory of distributed computing, computational geometry, and complexity.

News and Events

• Weekly Theory Seminar
• MSRA Theory Workshop, April 2008

Visitors and Collaborators

• Prof. Jin-Yi Cai, University of Wisconsin at Madison, USA
• Dr. Li Zhang, Microsoft Research Silicon Valley, USA
• Prof. Shang-Hua Teng, Boston University and Microsoft Research, 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

Recent Publications

1. 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.

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]

3. 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]

4. 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]
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.
6. 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]
7. 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]
8. 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.   
9. 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. 
10. Yingchao Zhao, Wei Chen, and Shang-Hua Teng. The isolation game: A game of distances. In Proceedings of the 19th International Symposium on Algorithms and Computation ( ISAAC'2008), Gold Coast, Australia, Dec. 2008. [pdf] [technical report: MSR-TR-2008-126]
11. 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]
12. 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]
13. 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]
14. 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]
15. 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]
16. 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]

• Overview
• People
• News and Events
• Visitors and Collaborators
• Recent Publications