Accueil

Pinyan Lu

  1. Correlation Decay up to Uniqueness in Spin Systems.

    Thu, 12/01/2011 - 15:01 — SomNambul
    Authors: Pinyan Lu, Liang Li, Yitong Yin
    Subjects: Data Structures and Algorithms
    Abstract

    We give a complete characterization of the two-state anti-ferromagnetic spin
    systems which are of exponential correlation decay. We show that a system is of
    correlation decay on all graphs with maximum degree \Delta\ if and only if the
    system has a unique Gibbs measure on all infinite regular trees up to degree
    \Delta, where \Delta\ can either be bounded or unbounded.

  2. Holographic Algorithms with Matchgates Capture Precisely Tractable Planar #CSP.

    Thu, 08/05/2010 - 15:01 — SomNambul
    Authors: Jin-Yi Cai, Pinyan Lu, Mingji Xia
    Subjects: Computational Complexity
    Abstract

    Valiant introduced matchgate computation and holographic algorithms. A number
    of seemingly exponential time problems can be solved by this novel algorithmic
    paradigm in polynomial time. We show that, in a very strong sense, matchgate
    computations and holographic algorithms based on them provide a universal
    methodology to a broad class of counting problems studied in statistical
    physics community for decades. They capture precisely those problems which are
    #P-hard on general graphs but computable in polynomial time on planar graphs.

  3. On the Approximability of Budget Feasible Mechanisms.

    Fri, 07/23/2010 - 15:01 — SomNambul
    Authors: Ning Chen, Nick Gravin, Pinyan Lu
    Subjects: Computer Science and Game Theory
    Abstract

    Budget feasible mechanisms, recently initiated by Singer (FOCS 2010), extend
    algorithmic mechanism design problems to a realistic setting with a budget
    constraint. We consider the problem of designing truthful budget feasible
    mechanisms for general submodular functions: we give a randomized mechanism
    with approximation ratio $7.91$ (improving the previous best-known result 112),
    and a deterministic mechanism with approximation ratio $8.34$.

  4. Pricing in Social Networks: Equilibrium and Revenue Maximization.

    Mon, 07/12/2010 - 15:01 — SomNambul
    Authors: Wei Chen, Pinyan Lu, Xiaorui Sun, Yajun Wang, Zeyuan Allen Zhu
    Subjects: Computer Science and Game Theory
    Abstract

    We study the revenue maximization problem in selling a digital product in a
    social network where social influence affects agents' purchasing decisions. The
    utility of each agent consists of two parts: her intrinsic value on the
    product, and the linearly additive influence from other agents in the network.
    We consider the simultaneous-move game where all agents make decisions
    simultaneously.

  5. From Holant To #CSP And Back: Dichotomy For Holant$^c$ Problems.

    Wed, 04/07/2010 - 15:02 — SomNambul
    Authors: Jin-Yi Cai, Sangxia Huang, Pinyan Lu
    Subjects: Computational Complexity
    Abstract

    We explore the intricate interdependent relationship among counting problems,
    considered from three frameworks for such problems: Holant Problems, counting
    CSP and weighted H-colorings. We consider these problems for general complex
    valued functions that take boolean inputs. We show that results from one
    framework can be used to derive results in another, and this happens in both
    directions. Holographic reductions discover an underlying unity, which is only
    revealed when these counting problems are investigated in the complex domain
    $\mathbb{C}$.

Math-arch

Syndicate content