# 学术报告通知

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 ZA(G), where for an arbitrary input graph G, ZA(G) = ?x:V(G) ? [m]? (u, v) ? E(G) Ax (u), x (v).

Our focus is the computational complexity of ZA(G). With Xi Chen and Pinyan Lu, we have achieved a complete classification theorem for the complexity of ZA(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.

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.

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.

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.

## 相关链接

• C-FAIR
• 时空视点传媒
• ,澳门新葡新京官网中加合作办学项目
• 电子商务交易技术国家工程实验室