Seminar on May 26, 2011

Date: May 26, 2011.

Place: Xi'an Jiaotong-Liverpool University, Suzhou


Title: Challenges in Algorithmic Game Theory and Applications

Speaker: Xiaotie Deng (Liverpool University)

The interface of algorithms and game theory has motivated growing research activities in the last ten years, driven by applications in Internet markets, rise of social networks, as well as agent theories and practices. I discuss several key issues in theory and applications of this ever expanding field.

Title: Non-negatively Weighted #CSP: An Effective Complexity Dichotomy

Speaker: Xi Chen (Columbia University)


We prove a complexity dichotomy theorem for all non-negatively weighted counting Constraint Satisfaction Problems (#CSP). This caps a long series of important results on counting problems including unweighted and weighted graph homomorphisms and the celebrated dichotomy theorem for unweighted #CSP. Our dichotomy theorem gives a succinct criterion for tractability. If a set F of constraint functions satisfies the criterion, then the #CSP problem defined by F is solvable in polynomial time; if F does not satisfy the criterion, then the problem is #P-hard. We furthermore show that the question of whether F satisfies the criterion is decidable in NP.

Surprisingly, our tractability criterion is simpler than the previous criteria for the more restricted classes of problems, although when specialized to those cases, they are logically equivalent. Our proof mainly uses Linear Algebra, and represents a departure from Universal Algebra, the dominant methodology in recent years.

Joint work with Jin-Yi Cai and Pinyan Lu.

Title: From stable matching to competitive equilibrium: incentives and computation

Speaker: Ning Chen (Nanyang Technological University)


Stable matching and competitive equilibrium are two well-studied solution concepts in Economics and have extensive applications in matching marketplaces. In the talk, we will review their mathematical structures, economic properties, and algorithmic computations, showing similarities between the two concepts. We will further discuss extensions of these concepts with their incentive and computational aspects, motivated from the emerging marketplaces, like sponsored search, online dating, and social lending, enabled by the Internet.

Title: Algorithms for Computing Conserved Gene Clusters

Speaker: Hon Wai LEONG (National University of Singapore)


Conserved gene clusters (CGC) are groups of genes that are located close together in the genomes of closely-related species. These conserved gene clusters are important in biology because their genes tend to code for proteins that have functional interactions. Thus, the identification of conserved gene clusters is an important step towards understanding genome evolution and predicting gene function.

Algorithmically, this gives rise to a new class of string problems where we are interested in sets of characters that are found in close proximity in multiple strings. In this talk, we survey several combinatorial models of CGC including the common-interval GC, gene teams, and r-window GC. We present efficient algorithms for computing CGC based on these models and also present some related open questions.

(This is joint work with Melvin Zhang)