学术报告（一）：Complexity Theory-The World of P and NP

报告人：美国威斯康星大学蔡进一教授

报告时间：5月28号9:30-10:30

报告地点：软件园校区高性能计算中心第一学术报告厅

报告摘要：The study of computational complexity presents challenging mathematical problems. In Complexity Theory computational problems are classified into complexity classes, the best known include P, NP and Valiant’s class #P for counting problems. A central problem in Valiant’s theory is the permanent vs. determinant problem. We will report some latest progress on this problem.

    Graph homomorphism was introduced by Lovasz over 40 years ago, and it is also called the partition functions in Statistical Physics, and can encode a rich class of counting problems: Given an m*m symmetric matrix A over the complex numbers, compute the function Z_A(G), where for an arbitrary input graph G, Z_A(G) = å_{x:V(G) ® [m]}Õ _{(u, v) Î E(G)} A_{x (u), x (v)}.

Our focus is the computational complexity of Z_A(G). With Xi Chen and Pinyan Lu, we have achieved a complete classification theorem for the complexity of Z_A(G). The classification proof is too complicated to present, but we will present the proof of a lemma. It states that in order to be computable in polynomial time, the matrix A must possess a group structure. Another component of the proof uses Gauss sums.  (In a subsequent Number Theory Seminar I will present some related work.)

    No prior knowledge of complexity theory is assumed.

报告人简介：蔡进一教授毕业于复旦大学，1986年在康奈尔大学取得博士学位。蔡进一教授曾在耶鲁大学、普林斯顿大学、SUNY Buffalo大学任教，现为威斯康星大学计算机科学系教授。蔡进一教授曾获总统青年科学家奖、计算机科学Alfred P. Sloan奖、晨兴数学银奖和颁发给美国资深科学家的Humboldt研究奖等多种奖项。蔡进一教授是美国计算机协会院士和AAAS Fellow。

蔡进一教授担任《Journal of Complexity》和《Journal of Computer and Systems Sciences》(JCSS)副主编，《International Journal of Foundations of Computer Science》和《The Chicago Journal of Theoretical Computer Science》编辑，《International Journal of Software and Informatics》领域编辑。蔡进一教授从事计算复杂性理论的研究，发表超过100篇研究论文。

学术报告（二）：Asymptotically Optimal Strategy-Proof Mechanisms for Two-Facility Games

报告人：微软亚洲研究院理论组陆品燕博士

报告时间：5月28号10：30-11：00

报告地点：软件园校区高性能计算中心第一学术报告厅

报告摘要：We consider the problem of locating facilities in a metric space to serve a set of selfish agents. The cost of an agent is the distance between her own location and the nearest facility. The social cost is the total cost of the agents. We are interested in designing strategy-proof mechanisms without payment that have a small approximation ratio for social cost. A mechanism is a (possibly randomized) algorithm which maps the locations reported by the agents to the locations of the facilities. A mechanism is strategy-proof if no agent can benefit from misreporting her location in any configuration.

We first prove an Ω(n) lower bound of the social cost approximation ratio for deterministic strategy-proof mechanisms. Our lower bound even holds for the line metric space. This significantly improves the previous constant lower bounds.  Notice that there is a matching linear upper bound in the line metric space. Next, we provide the first randomized strategy-proof mechanism with a constant approximation ratio of 4. Our mechanism works in general metric spaces. For randomized strategy-proof mechanisms, the previous best upper bound is O(n) which works only in the line metric space.

报告人简介：陆品燕博士是微软亚洲研究院理论组副研究员。于2005年和2009年在清华大学获计算机科学学士和博士学位，导师是姚期智教授和蔡进一教授。研究兴趣包括计算复杂性理论，算法设计和算法博弈论。在国际顶级会议和期刊发表论文多篇，其中论文Holographic Algorithms: The Power of Dimensionality Resolved获ICALP 2007最佳论文奖（合作者：蔡进一教授）。

学术报告（三）：Pareto Stability in Matching Marketplaces

报告人：新加坡南洋理工大学陈宁博士

报告时间：5月28号11：00-11：30

报告地点：软件园校区高性能计算中心第一学术报告厅

报告摘要：Motivated by online matching marketplaces such as social lending, we study markets where capacity-constrained bidders participate in multiple auctions that they have preferences over. While bidders have explicit preferences over auctions, we observe that the auctioneer side of the market has implicit preferences over bidders induced by the bids; this allows us to model these marketplaces in a matching framework with two-sided preferences.

The problem of clearing the market leads naturally to the algorithmic question of computing Pareto-optimal stable matchings in a many-to-many setting with ties and incomplete lists. We will provide a fast algorithm for computing Pareto-stable assignments for this very general multi-unit matching problem with arbitrary preference lists on both sides, with running time that is polynomial in the number of agents in the market, rather than the sum of capacities of all agents.

报告人简介：陈宁博士在华盛顿大学获博士学位，导师是Anna Karlin教授。现为新加坡南洋理工大学数学科学系的助理教授。研究兴趣包括算法博弈论和计算经济学，Internet的算法和经济问题，以及算法和组合优化。

学术报告（四）：Social networks and beyond --- Our recent work on

报告人：微软亚洲研究院理论组首席研究员陈卫博士

报告时间：5月28号14：00-15：00

报告地点：软件园校区高性能计算中心第一学术报告厅

报告摘要：With the increasing popularity of online social network sites such as Facebook, Myspace, and Twitter, many new research opportunities are presented in understanding the social networking phenomenon and harnessing the power of social networks for commerce or social welfare. In this talk, I will survey several studies I and my collaborators conducted recently on social networks or other related complex networks. The topics include: (a) scalable influence maximization for viral marketing in social networks; (b) bounded-budget betweenness centrality (B3C) game for network formation; and (c) distance oracle and compact routing in power-law graphs.

报告人简介：陈卫博士于清华大学计算机科学系获学士和硕士学位，于康奈尔大学计算机科学系获博士学位，现为微软亚洲研究院理论组首席研究员，清华大学客座教授，并担任清华大学姚期智教授领导的理论计算机科学研究所博士生联合导师。主要研究兴趣包括分布式计算，容错系统和理论，算法博弈论和社会网络中的算法问题。在国际领先的期刊和会议上发表了大量研究论文，获2000年IEEE/IFIP Dependable Systems and Networks国际会议William C. Carter奖。

学术报告（五）：Compact Routing in Power-Law Graphs

报告人：微软亚洲研究院理论组王亚军博士

报告时间：5月28号15：00-15：30

报告地点：软件园校区高性能计算中心第一学术报告厅

报告摘要：We adapt the compact routing scheme by Thorup and Zwick to optimize it for power-law graphs. We analyze our adapted routing scheme based on the theory of unweighted random power-law graphs with fixed expected degree sequence by Aiello, Chung, and Lu. Our result is the first theoretical bound coupled to the parameter of the power-law graph model for a compact routing scheme.

In particular, we prove that, for stretch 3, instead of routing tables with O(n^{1/2}) bits as in the general scheme by Thorup and Zwick, expected sizes of O(n^\gamma log n) bits are sufficient, and that all the routing tables can be constructed at once in expected time O(n^{1+\gamma} log n), with \gamma = (\tau-2)/(2\tau-3) where \tau \in (2, 3) is the power-law exponent. Both bounds also hold with probability at least 1-1/n. The routing scheme is a labeled scheme, requiring a stretch-5 handshaking step and using addresses and message headers with O(log n log log n) bits, with probability at least 1-o(1).

We further demonstrate the effectiveness of our scheme by simulations on real-world graphs as well as synthetic power-law graphs. With the same techniques as for the compact routing scheme, we also adapt the approximate distance oracle by Thorup and Zwick for stretch 3 and obtain a new upper bound of expected O(n^{1+\gamma}) for space and preprocessing.

报告人简介：王亚军博士在中国科技大学获计算机科学学士学位，2008年在香港科技大学获博士学位，于2008年加入微软亚洲研究院理论组。研究兴趣包括计算几何、社会网络和算法博弈论。