Pinyan Lu

I&C Journal 2026 Journal Article

Dichotomy for Holant* problems with one ternary function on domain size 3

• Jin-Yi Cai
• Pinyan Lu
• Mingji Xia

Holant problems are a general framework to study the algorithmic complexity of counting problems. Both counting constraint satisfaction problems and graph homomorphisms are special cases. All previous results of Holant problems are over the Boolean domain. 3 In this paper, we give the first dichotomy theorem for Holant problems for domain size >2. We discover unexpected tractable families of counting problems, by giving new polynomial time algorithms. This paper also initiates holographic reductions in domains of size >2. This is our main algorithmic technique, and is used for both tractable families and hardness reductions. The dichotomy theorem is the following: For any complex-valued symmetric function F with arity 3 on domain size 3, we give an explicit criterion on F, such that if F satisfies the criterion then the problem Holant ⁎ ( F ) is computable in polynomial time; otherwise Holant ⁎ ( F ) is #P-hard.

AIJ Journal 2026 Journal Article

Incentives for early arrival in online cooperative games

• Dengji Zhao
• Yaoxin Ge
• Yao Zhang
• Zhihao Gavin Tang
• Hu Fu
• Pinyan Lu

• We formalize a new concept of Incentives for Early Arrival (I4EA) in online cooperative games where players join sequentially. • We propose the very first mechanism called Rewarding First Critical players (RFC) to satisfy I4EA in 0–1 valued monotone games. • We propose an online decomposition of monotone games into 0–1 valued games, generalizing RFC while preserving properties. • The conference version won the best paper award at AAMAS 2024. This extended version adds an efficient algorithm for RFC and expands future directions. We study cooperative games where players join sequentially, and the value generated by those who have joined at any point must be irrevocably divided among these players. We introduce two desiderata for the value division mechanism: that the players should have incentives to join as early as possible, and that the division should be considered fair. For the latter, we require that each player’s expected share in the mechanism should equal her Shapley value if the players’ arrival order is uniformly at random. When the value generation function is submodular, allocating the marginal value to the player satisfies these properties. This is no longer true for more general functions. Our main technical contribution is a complete characterization of 0–1 value games for which desired mechanisms exist. We show that a natural mechanism, Rewarding First Critical Player (RFC), is complete, in that a 0–1 value function admits a mechanism with the properties above if and only if RFC satisfies them; we analytically characterize all such value functions. Moreover, we give an algorithm that decomposes, in an online fashion, any value function into 0–1 value functions, on each of which RFC can be run. In this way, we design an extension of RFC for general monotone games, and the properties are proved to be maintained.

ICLR Conference 2025 Conference Paper

Bandit Learning in Matching Markets with Indifference

• Fang Kong 0002
• Jingqi Tang
• Mingzhu Li
• Pinyan Lu
• John C. S. Lui
• Shuai Li 0010

A rich line of recent works studies how participants in matching markets learn their unknown preferences through iterative interactions with each other. The two sides of participants in the market can be respectively formulated as players and arms in the bandit problem. To ensure market stability, the objective is to minimize the stable regret of each player. Though existing works provide significant theoretical upper bounds for players' stable regret, the results heavily rely on the assumption that each participant has a strict preference ranking. However, in real applications, multiple candidates (e.g., workers in the labor market and students in school admission) usually demonstrate comparable performance levels, making it challenging for participants (e.g., employers and schools) to differentiate and rank their preferences. To deal with the potential indifferent preferences, we propose an adaptive exploration algorithm based on arm-guided Gale-Shapley (AE-AGS). We show that its stable regret is of order $O(NK \log T / \Delta^2)$, where $N$ is the number of players, $K$ the number of arms, $T$ the total time horizon, and $\Delta$ the minimum non-zero preference gap. Extensive experiments demonstrate the algorithm's effectiveness in handling such complex situations and its consistent superiority over baselines.

SODA Conference 2025 Conference Paper

Coresets for Constrained Clustering: General Assignment Constraints and Improved Size Bounds

• Lingxiao Huang
• Jian Li 0015
• Pinyan Lu
• Xuan Wu 0002

TMLR Journal 2025 Journal Article

Efficient Training of Multi-task Neural Solver for Combinatorial Optimization

• Chenguang Wang
• Zhang-Hua Fu
• Pinyan Lu
• Tianshu Yu

Efficiently training a multi-task neural solver for various combinatorial optimization problems (COPs) has been less studied so far. Naive application of conventional multi-task learning approaches often falls short in delivering a high-quality, unified neural solver. This deficiency primarily stems from the significant computational demands and a lack of adequate consideration for the complexities inherent in COPs. In this paper, we propose a general and efficient training paradigm to deliver a unified combinarotial multi-task neural solver. To this end, we resort to the theoretical loss decomposition for multiple tasks under an encoder-decoder framework, which enables more efficient training via proper bandit task-sampling algorithms through an intra-task influence matrix. By employing theoretically grounded approximations, our method significantly enhances overall performance, regardless of whether it is within constrained training budgets, across equivalent training epochs, or in terms of generalization capabilities, when compared to conventional training schedules. On the real-world datasets of TSPLib and CVRPLib, our method also achieved the best results compared to single task learning and multi-task learning approaches. Additionally, the influence matrix provides empirical evidence supporting common practices in the field of learning to optimize, further substantiating the effectiveness of our approach. Our code is open-sourced and available at \url{https://github.com/LOGO-CUHKSZ/MTL-COP}.

IJCAI Conference 2025 Conference Paper

Incentives for Early Arrival in Cooperative Games (Extended Abstract)

• Yaoxin Ge
• Yao Zhang
• Dengji Zhao
• Zhihao Gavin Tang
• Hu Fu
• Pinyan Lu

We study cooperative games where players join sequentially, and the value generated by those who have joined at any point must be irrevocably divided among these players. We introduce two desiderata for the value division mechanism: that the players should have incentives to join as early as possible, and that the division should be considered fair. For the latter, we require that each player's expected share in the mechanism should equal her Shapley value if the players' arrival order is uniformly at random. When the value generation function is submodular, allocating the marginal value to the player satisfies these properties. This is no longer true for more general functions. Our main technical contribution is a complete characterization of 0-1 value games for which desired mechanisms exist. We show that a natural mechanism, Rewarding First Critical Player (RFC), is complete, in that a 0-1 value function admits a mechanism with the properties above if and only if RFC satisfies them; we analytically characterize all such value functions. Moreover, we give an algorithm that decomposes, in an online fashion, any value function into 0-1 value functions, on each of which RFC can be run. In this way, we design an extension of RFC for general monotone games, and the properties are proved to be maintained.

AAMAS Conference 2025 Conference Paper

Incentives for Early Arrival in Cost Sharing

• Junyu Zhang
• Yao Zhang
• Yaoxin Ge
• Dengji Zhao
• Hu Fu
• Zhihao Gavin Tang
• Pinyan Lu

In cooperative games, we study how values created or costs incurred by a coalition are shared among the members within it, and the players may join the coalition in a online manner such as investors invest a startup. Recently, Ge et al. [10] proposed a new property called incentives for early arrival (I4EA) in such games, which says that the online allocation of values or costs should incentivize agents to join early in order to prevent mutual strategic waiting. Ideally, the allocation should also be fair, so that agents arriving in an order uniformly at random should expect to get/pay their Shapley values. Ge et al. [10] showed that not all monotone value functions admit such mechanisms in online value sharing games. In this work, we show a sharp contrast in online cost sharing games. We construct a mechanism with all the properties mentioned above, for every monotone cost function. To achieve this, we first solve 0-1 valued cost sharing games with a novel mechanism called Shapley-fair shuffle cost sharing mechanism (SFS-CS), and then extend SFS-CS to a family called generalized Shapley-fair shuffle cost sharing mechanisms (GSFS-CS). The critical technique we invented here is a mapping from one arrival order to another order so that we can directly apply marginal cost allocation on the shuffled orders to satisfy the properties. Finally, we solve general valued cost functions, by decomposing them into 0-1 valued functions in an online fashion.

AAAI Conference 2025 Conference Paper

Optimal Auction Design for Mixed Bidders

• Xiaohui Bei
• Pinyan Lu
• Zhiqi Wang
• Tao Xiao
• Xiang Yan

The predominant setting in classic auction theory considers bidders as utility maximizers (UMs), who aim to maximize quasi-linear utility functions. Recent autobidding strategies in online advertising have sparked interest in auction design with value maximizers (VMs), who aim to maximize the total value obtained. In this work, we investigate revenue-maximizing auction design for selling a single item to a mix of UMs and VMs. Crucially, we assume the UM/VM type is private information of a bidder. This shift to a multi-parameter domain complicates the design of incentive compatible mechanisms. Under this setting, we first characterize the optimal auction structure for auctions with a single bidder. We observe that the optimal auction moves gradually from a first-price auction to a Myerson auction as the probability of the bidder being a UM increases from 0 to 1. We also extend our study to multi-bidder setting and present an algorithm for deriving the optimal lookahead auction with multiple mixed types of bidders.

I&C Journal 2025 Journal Article

Two-state spin systems with negative interactions

• Yumou Fei
• Leslie Ann Goldberg
• Pinyan Lu

We study the approximability of computing the partition functions of two-state spin systems. The problem is parameterized by a 2 × 2 symmetric matrix. Previous results on this problem were restricted either to the case where the matrix has non-negative entries, or to the case where the diagonal entries are equal, i. e. Ising models. In this paper, we study the generalization to arbitrary 2 × 2 interaction matrices with real entries. We show that in some regions of the parameter space, it's #P-hard to even determine the sign of the partition function, while in other regions there are fully polynomial approximation schemes for the partition function. Our results reveal several new computational phase transitions.

FOCS Conference 2024 Conference Paper

Benchmark-Tight Approximation Ratio of Simple Mechanism for a Unit-Demand Buyer

• Yaonan Jin
• Pinyan Lu

We study revenue maximization in the unit-demand single-buyer setting. Our main result is that Uniform-Ironed-Virtual-Value Item Pricing guarantees a tight 3-approximation to the Duality Relaxation Benchmark [Chawla-Malec-Sivan, EC’10/GEB’15; Cai-Devanur-Weinberg, STOC’16/ SICOMP’21], breaking the barrier of 4 since [Chawla-Hartline-Malec-Sivan, STOC’10; Chawla-Malec-Sivan, EC’10/GEB’15]. To our knowledge, this is the first benchmark-tight revenue guarantee of any simple multi-item mechanism. Technically, all previous works employ Myerson Auction as an intermediary. The barrier of 4 follows as Uniform-Ironed-Virtual-Value Item Pricing achieves a tight 2-approximation to Myerson Auction, which then achieves a tight 2-approximation to Duality Relaxation Benchmark. Instead, our new approach avoids Myerson Auction, thus enabling the improvement. Central to our work are a benchmark-based 3-competitive prophet inequality and its fully constructive proof. Such variant prophet inequalities shall find future applications, e. g. , to Multi-Item Mechanism Design where optimal revenues are relaxed to various more accessible benchmarks. We complement our benchmark-tight ratio with an impossibility result. All previous works and ours follow the single-dimensional representative approach introduced by [Chawla-Hartline-Kleinberg, EC'07]. Against Duality Relaxation Benchmark, it turns out that this approach cannot beat our bound of 3 for a large class of Item Pricing's.

IJCAI Conference 2024 Conference Paper

Improved Approximation of Weighted MMS Fairness for Indivisible Chores

• Fangxiao Wang
• Bo Li
• Pinyan Lu

We study how to fairly allocate a set of indivisible chores among n agents who may have different weights corresponding to their involvement in completing these chores. We found that some of the existing fairness notions may place agents with lower weights at a disadvantage, which motivates us to explore weighted maximin share fairness (WMMS). While it is known that a WMMS allocation may not exist, no non-trivial approximation has been discovered thus far. In this paper, we first design a simple sequential picking algorithm that solely relies on the agents’ ordinal rankings of the items, which achieves an approximation ratio of O(log n). Then, for the case involving two agents, we improve the approximation ratio to (√3+1)/2 ≈1. 366, and prove that it is optimal. We also consider an online setting when the items arrive one after another and design an O(√n)-competitive online algorithm given the valuations are normalized

AAMAS Conference 2024 Conference Paper

Incentives for Early Arrival in Cooperative Games

• Yaoxin Ge
• Yao Zhang
• Dengji Zhao
• Zhihao Gavin Tang
• Hu Fu
• Pinyan Lu

We study cooperative games where players join sequentially, and the value generated by those who have joined at any point must be irrevocably divided among these players. We introduce two desiderata for the value division mechanism: that the players should have incentives to join as early as possible, and that the division should be considered fair. For the latter, we require that each player’s expected share in the mechanism should equal her Shapley value if the players’ arrival order is uniformly at random. When the value generation function is submodular, allocating the marginal value to the player satisfies these properties. This is no longer true for more general functions. Our main technical contribution is a complete characterization of 0-1 value games for which desired mechanisms exist. We show that a natural mechanism, Rewarding First Critical Player (RFC), is complete, in that a 0-1 value function admits a mechanism with the properties above if and only if RFC satisfies them; we analytically characterize all such value functions. Moreover, we give an algorithm that decomposes, in an online fashion, any value function into 0-1 value functions, on each of which RFC can be run. In this way, we design an extension of RFC for general monotone games, and the properties are proved to be maintained.

SODA Conference 2023 Conference Paper

Bidder Subset Selection Problem in Auction Design

• Xiaohui Bei
• Nikolai Gravin
• Pinyan Lu
• Zhihao Gavin Tang

Motivated by practical concerns in the online advertising industry, we study a bidder subset selection problem in single-item auctions. In this problem, a large pool of candidate bidders have independent values sampled from known prior distributions. The seller needs to pick a subset of bidders and run a given auction format on the selected subset to maximize her expected revenue. We propose two frameworks for the subset restrictions: (i) capacity constraint on the set of selected bidders; and (ii) incurred costs for the bidders invited to the auction. For the second-price auction with anonymous reserve (SPA-AR), we give constant approximation polynomial time algorithms in both frameworks (in the latter framework under mild assumptions about the market). Our results are in stark contrast to the previous work of Mehta, Nadav, Psomas, Rubinstein [NeurIPS 2020], who showed hardness of approximation for the SPA without a reserve price. We also give complimentary approximation results for other well-studied auction formats such as anonymous posted pricing and sequential posted pricing. On a technical level, we find that the revenue of SPA-AR as a set function f ( S ) of its bidders S is fractionally-subadditive but not submodular. Our bidder selection problem with invitation costs is a natural question about (approximately) answering a demand oracle for f (·) under a given vector of costs, a common computational assumption in the literature on combinatorial auctions. * This work is supported by Science and Technology Innovation 2030 –“New Generation of Artificial Intelligence” Major Project No. (2018AAA0100903), Innovation Program of Shanghai Municipal Education Commission, Program for Innovative Research Team of Shanghai University of Finance and Economics (IRTSHUFE) and the Fundamental Research Funds for the Central Universities. Zhihao Gavin Tang is supported by NSFC grant 61902233. Nick Gravin is supported by NSFC grant 62150610500.

ICLR Conference 2023 Conference Paper

Revocable Deep Reinforcement Learning with Affinity Regularization for Outlier-Robust Graph Matching

• Chang Liu 0021
• Zetian Jiang
• Runzhong Wang
• Lingxiao Huang
• Pinyan Lu
• Junchi Yan

Graph matching (GM) has been a building block in various areas including computer vision and pattern recognition. Despite recent impressive progress, existing deep GM methods often have obvious difficulty in handling outliers, which are ubiquitous in practice. We propose a deep reinforcement learning based approach RGM, whose sequential node matching scheme naturally fits the strategy for selective inlier matching against outliers. A revocable action framework is devised to improve the agent's flexibility against the complex constrained GM. Moreover, we propose a quadratic approximation technique to regularize the affinity score, in the presence of outliers. As such, the agent can finish inlier matching timely when the affinity score stops growing, for which otherwise an additional parameter i.e. the number of inliers is needed to avoid matching outliers. In this paper, we focus on learning the back-end solver under the most general form of GM: the Lawler's QAP, whose input is the affinity matrix. Especially, our approach can also boost existing GM methods that use such input. Experiments on multiple real-world datasets demonstrate its performance regarding both accuracy and robustness.

SODA Conference 2023 Conference Paper

The Price of Stability for First Price Auction

• Yaonan Jin
• Pinyan Lu

This paper establishes the Price of Stability (PoS) for First Price Auctions, for all equilibrium concepts that have been studied in the literature: Bayesian Nash Equilibrium ⊊ Bayesian Correlated Equilibrium ⊊ Bayesian Coarse Correlated Equilibrium. • Bayesian Nash Equilibrium: For independent valuations, the tight PoS is 1 − 1/ e 2 ≈ 0. 8647, matching the counterpart Price of Anarchy (PoA) bound [JL22]. For correlated valuations, the tight PoS is 1 − 1/ e ≈ 0. 6321, matching the counterpart PoA bound [ST13, Syr14]. This result indicates that, in the worst cases, efficiency degradation depends not on different selections among Bayesian Nash Equilibria. • Bayesian (Coarse) Correlated Equilibrium: For independent or correlated valuations, the tight PoS is always 1 = 100%, i. e. , no efficiency degradation. This result indicates that First Price Auctions can be fully efficient when we allow the more general equilibrium concepts. * The full version of the paper can be accessed at https: //arxiv. org/abs/2207. 04455

TCS Journal 2022 Journal Article

An FPTAS for the hardcore model on random regular bipartite graphs

• Chao Liao
• Jiabao Lin
• Pinyan Lu
• Zhenyu Mao

We give a fully polynomial-time approximation scheme (FPTAS) to compute the partition function of the hardcore model of fugacity λ on random Δ-regular bipartite graphs for all sufficiently large Δ and λ ≥ 4 ( log ⁡ Δ ) 3 / Δ. For the special case of λ = 1, where the partition function computes the number of independent sets, an FPTAS exists for Δ ≥ 50. Our technique is based on the polymer model, which is used by Jenssen, Keevash and Perkins (SODA, 2019) to obtain an FPTAS for #BIS-hard problems for the first time. The technique also applies to counting q-colorings: For q ≥ 3 and Δ ≥ Δ ( q ), there is an FPTAS to compute the number of q-colorings on random Δ-regular bipartite graphs.

AIJ Journal 2022 Journal Article

Bayesian auctions with efficient queries

• Jing Chen
• Bo Li
• Yingkai Li
• Pinyan Lu

Designing dominant-strategy incentive compatible (DSIC) mechanisms for a seller to generate (approximately) optimal revenue by selling items to players is a fundamental problem in Bayesian mechanism design. However, most existing studies assume that the seller knows the entire distribution from which the players' values are drawn. Unfortunately, this assumption may not hold in reality: for example, when the distributions have exponentially large supports or do not have succinct representations. In this work we consider, for the first time, the query complexity of Bayesian mechanisms. The seller only has limited oracle accesses to the players' distributions, via quantile queries and value queries. For single-item auctions, we design mechanisms with logarithmic number of value or quantile queries which achieve almost optimal revenue. We then prove logarithmic lower-bounds, i. e. , logarithmic number of queries are necessary for any constant approximation DSIC mechanisms, even when randomized and adaptive queries are allowed. Thus our mechanisms are almost optimal regarding query complexity. Our lower-bounds can be extended to multi-item auctions with monotone subadditive valuations, and we complement this part with constant approximation mechanisms for unit-demand or additive valuation functions. Our results are robust even if the answers to the queries contain noises. Thus, in those settings the seller needs to access much less than the entire distribution to achieve approximately optimal revenue.

IJCAI Conference 2022 Conference Paper

Bayesian Auctions with Efficient Queries (Extended Abstract)

• Jing Chen
• Bo Li
• Yingkai Li
• Pinyan Lu

Designing dominant-strategy incentive compatible (DSIC) mechanisms for a seller to generate (approximately) optimal revenue by selling items to players is a fundamental problem in Bayesian mechanism design. However, most existing studies assume that the seller knows the entire distribution from which the players’ values are drawn. Unfortunately, this assumption may not hold in reality: for example, when the distributions have exponentially large supports or do not have succinct representations. In this work we consider, for the first time, the query complexityof Bayesian mechanisms. The seller only has limited oracle accesses to the players’ distributions, via quantile queriesand value queries. For single-item auctions, we design mechanisms with logarithmicnumber of value or quantile queries which achieve almost optimal revenue. We then prove logarithmic lower-bounds, i. e. , logarithmic number of queries are necessary for any constant approximation DSIC mechanisms, even when randomized and adaptive queries are allowed. Thus our mechanisms are almost optimal regarding query complexity. Our lower-bounds can be extended to multi-item auctions with monotone subadditive valuations, and we complement this part with constant approximation mechanisms for unit-demand or additive valuation functions. Our results are robust even if the answers to the queries contain noises.

FOCS Conference 2022 Conference Paper

First Price Auction is 1 - 1 /e 2 Efficient

• Yaonan Jin
• Pinyan Lu

We prove that the PoA of First Price Auctions is 1-1/$ e^{2}\approx$0. 8647, closing the gap between the best known bounds [0. 7430, 0. 8689].

IJCAI Conference 2022 Conference Paper

Mechanism Design with Predictions

• Chenyang Xu
• Pinyan Lu

Improving algorithms via predictions is a very active research topic in recent years. This paper initiates the systematic study of mechanism design in this model. In a number of well-studied mechanism design settings, we make use of imperfect predictions to design mechanisms that perform much better than traditional mechanisms if the predictions are accurate (consistency), while always retaining worst-case guarantees even with very imprecise predictions (robustness). Furthermore, we refer to the largest prediction error sufficient to give a good performance as the error tolerance of a mechanism, and observe that an intrinsic tradeoff among consistency, robustness and error tolerance is common for mechanism design with predictions.

SODA Conference 2021 Conference Paper

Approximating Permanent of Random Matrices with Vanishing Mean: Made Better and Simpler

• Zhengfeng Ji
• Zhihan Jin
• Pinyan Lu

The algorithm and complexity of approximating the permanent of a matrix is an extensively studied topic. Recently, its connection with quantum supremacy and more specifically BosonSampling draws a special attention to the average-case approximation problem of the permanent of random matrices with zero or small mean value for each entry. Eldar and Mehraban (FOCS 2018) gave a quasi-polynomial time algorithm for random matrices with mean at least 1/polyloglog( n ). In this paper, we improve the result by designing a deterministic quasi-polynomial time algorithm and a PTAS for random matrices whose module of mean is at least 1/ polylog( n ). We note that if the algorithm can be further improved to work with a mean value that is a sufficiently small 1/poly( n ), it will disprove a central conjecture for quantum supremacy. Our algorithm is also much simpler and has a better and flexible trade-off for running time. The running time can be quasi-polynomial in both n and 1/ ∊, or PTAS (polynomial in n but exponential in 1/ ∊ ), where ∊ is the approximation parameter.

SODA Conference 2021 Conference Paper

Concentration bounds for almost k -wise independence with applications to non-uniform security

• Nikolai Gravin
• Siyao Guo 0001
• Tsz Chiu Kwok
• Pinyan Lu

We prove a few concentration inequalities for the sum of n binary random variables under weaker conditions than k -wise independence. Namely, we consider two standard conditions that are satisfied in many applications: (a) direct product conditions (b) the XOR condition. Both conditions are weaker than mutual independence and both imply strong concentration bounds (similar to Chernoff-Hoeffding) on the tail probability of the sum of bounded random variables ([Impagliazzo and Kabanets, APPROX-RANDOM 10], [Unger, FOCS 09]). Our inequalities can be stated as the implication of threshold direct product theorems from either k -wise direct product conditions, or the k -wise XOR condition. By proving optimality of our inequalities, we show a clear separation for k « n between k -wise product conditions and XOR condition as well as a stark contrast between k -wise and n -wise product theorems. We use these bounds in the cryptographic application that provides provable security against algorithms with S -bit advice. Namely, we show how the problem reduces to proving S -wise direct product theorems or S -wise XOR lemmas for certain ranges of parameters. Finally, we derive a new S -wise XOR lemma, which yields a tight non-uniform bound for length increasing pseudorandom generators, resolving a 10-year-old open problem from [De, Trevisan, and Tulsiani, CRYPTO 10].

ICML Conference 2021 Conference Paper

Online Selection Problems against Constrained Adversary

• Zhihao Jiang
• Pinyan Lu
• Zhihao Gavin Tang
• Yuhao Zhang 0001

Inspired by a recent line of work in online algorithms with predictions, we study the constrained adversary model that utilizes predictions from a different perspective. Prior works mostly focused on designing simultaneously robust and consistent algorithms, without making assumptions on the quality of the predictions. In contrary, our model assumes the adversarial instance is consistent with the predictions and aim to design algorithms that have best worst-case performance against all such instances. We revisit classical online selection problems under the constrained adversary model. For the single item selection problem, we design an optimal algorithm in the adversarial arrival model and an improved algorithm in the random arrival model (a. k. a. , the secretary problem). For the online edge-weighted bipartite matching problem, we extend the classical Water-filling and Ranking algorithms and achieve improved competitive ratios.

UAI Conference 2021 Conference Paper

Variance-dependent best arm identification

• Pinyan Lu
• Chao Tao
• Xiaojin Zhang 0002

We study the problem of identifying the best arm in a stochastic multi-armed bandit game. Given a set of $n$ arms indexed from $1$ to $n$, each arm $i$ is associated with an unknown reward distribution supported on $[0, 1]$ with mean $\theta_i$ and variance $\sigma_i^2$. Assume $\theta_1 > \theta_2 \geq \cdots \geq\theta_n$. We propose an adaptive algorithm which explores the gaps and variances of the rewards of the arms and makes future decisions based on the gathered information using a novel approach called grouped median elimination. The proposed algorithm guarantees to output the best arm with probability $(1-\delta)$ and uses at most $O \left(\sum_{i = 1}^n \left(\frac{\sigma_i^2}{\Delta_i^2} + \frac{1}{\Delta_i}\right)(\ln \delta^{-1} + \ln \ln \Delta_i^{-1})\right)$ samples, where $\Delta_i$ ($i \geq 2$) denotes the reward gap between arm $i$ and the best arm and we define $\Delta_1 = \Delta_2$. This achieves a significant advantage over the variance-independent algorithms in some favorable scenarios and is the first result that removes the extra $\ln n$ factor on the best arm compared with the state-of-the-art. We further show that $\Omega \left( \sum_{i = 1}^n \left( \frac{\sigma_i^2}{\Delta_i^2} + \frac{1}{\Delta_i} \right) \ln \delta^{-1} \right)$ samples are necessary for an algorithm to achieve the same goal, thereby illustrating that our algorithm is optimal up to doubly logarithmic terms.

IJCAI Conference 2020 Conference Paper

Strategyproof Mechanism for Two Heterogeneous Facilities with Constant Approximation Ratio

• Minming Li
• Pinyan Lu
• Yuhao Yao
• Jialin Zhang

In this paper, we study the two-facility location game with optional preference where the acceptable set of facilities for each agent could be different and an agent's cost is his distance to the closest facility within his acceptable set. The objective is to minimize the total cost of all agents while achieving strategyproofness. For general metrics, we design a deterministic strategyproof mechanism for the problem with approximation ratio of 1+2alpha, where alpha is the approximation ratio of the optimization version. In particular, for the setting on a line, we improve the earlier best ratio of n/2+1 to a ratio of 2. 75.

SODA Conference 2020 Conference Paper

Zeros of ferromagnetic 2-spin systems

• Heng Guo 0001
• Jingcheng Liu 0001
• Pinyan Lu

SODA Conference 2019 Conference Paper

Approximability of the Six-vertex Model

• Jin-Yi Cai
• Tianyu Liu 0002
• Pinyan Lu

We take the first step toward a classification of the approximation complexity of the six-vertex model. This is a subject of extensive research in statistical physics. Our result concerns the approximability of the partition function on 4-regular graphs, classified according to the parameters of the model. Our complexity results conform to the phase transition phenomenon from physics. We show that the approximation complexity of the six-vertex model behaves dramatically differently on the two sides separated by the phase transition threshold. Furthermore, we present structural properties of the six-vertex model on planar graphs for parameter settings that have known relations to the Tutte polynomial T ( G; x, y ).

SODA Conference 2019 Conference Paper

Correlation-Robust Analysis of Single Item Auction

• Xiaohui Bei
• Nikolai Gravin
• Pinyan Lu
• Zhihao Gavin Tang

We investigate the problem of revenue maximization in single-item auction within the new correlation-robust framework proposed by Carroll [2017] and further developed by Gravin and Lu [2018]. In this framework the auctioneer is assumed to have only partial information about marginal distributions, but does not know the dependency structure of the joint distribution. The auctioneer's revenue is evaluated in the worst-case over the uncertainty of possible joint distribution. For the problem of optimal auction design in the correlation robust-framework we observe that in most cases the optimal auction does not admit a simple form like the celebrated Myerson's auction for independent valuations. We analyze and compare performances of several DSIC mechanisms used in practice. Our main set of results concern the sequential posted-price mechanism (SPM). We show that SPM achieves a constant (4. 78) approximation to the optimal correlation-robust mechanism. We also show that in the symmetric (anonymous) case when all bidders have the same marginal distribution, (i) SPM has almost matching worst-correlation revenue as any second price auction with common reserve price, and (ii) when the number of bidders is large, SPM converges to optimum. In addition, we extend some results on approximation and computational tractability for lookahead auctions to the correlation-robust framework.

AAAI Conference 2019 Conference Paper

Learning Plackett-Luce Mixtures from Partial Preferences

• Ao Liu
• Zhibing Zhao
• Chao Liao
• Pinyan Lu
• Lirong Xia

We propose an EM-based framework for learning Plackett- Luce model and its mixtures from partial orders. The core of our framework is the efficient sampling of linear extensions of partial orders under Plackett-Luce model. We propose two Markov Chain Monte Carlo (MCMC) samplers: Gibbs sampler and the generalized repeated insertion method tuned by MCMC (GRIM-MCMC), and prove the efficiency of GRIM- MCMC for a large class of preferences. Experiments on synthetic data show that the algorithm with Gibbs sampler outperforms that with GRIM-MCMC. Experiments on real-world data show that the likelihood of test dataset increases when (i) partial orders provide more information; or (ii) the number of components in mixtures of Plackett- Luce model increases.

AAMAS Conference 2019 Conference Paper

Revenue Maximization with Imprecise Distribution

• Yingkai Li
• Pinyan Lu
• Haoran Ye

We study the revenue maximization problem with an imprecisely estimated distribution of a single buyer or several independent and identically distributed buyers given that this estimation is not far away from the true distribution. We use the earth mover’s distance to capture the estimation error between those two distributions in terms of both values and their probabilities, i. e. , the error in value space given a quantile, and the error in quantile space given a value. We give explicit characterization of the optimal mechanisms for the single buyer setting. For the multi-buyer case, we provide an algorithm that finds an approximately optimal mechanism (FPTAS) among the family of second price mechanisms with a fixed reserve.

STOC Conference 2019 Conference Paper

Tight approximation ratio of anonymous pricing

• Yaonan Jin
• Pinyan Lu
• Qi Qi 0003
• Zhihao Gavin Tang
• Tao Xiao

This paper considers two canonical Bayesian mechanism design settings. In the single-item setting, the tight approximation ratio of Anonymous Pricing is obtained: (1) compared to Myerson Auction, Anonymous Pricing always generates at least a 1/2.62-fraction of the revenue; (2) there is a matching lower-bound instance. In the unit-demand single-buyer setting, the tight approximation ratio between the simplest deterministic mechanism and the optimal deterministic mechanism is attained: in terms of revenue, (1) Uniform Pricing admits a 2.62-approximation to Item Pricing; (2) a matching lower-bound instance is presented also. These results answer two open questions asked by Alaei et al. (FOCS’15) and Cai and Daskalakis (GEB’15). As an implication, in the single-item setting: the approximation ratio of Second-Price Auction with Anonymous Reserve (Hartline and Roughgarden EC’09) is improved to 2.62, which breaks the best known upper bound of e ≈ 2.72.

SODA Conference 2019 Conference Paper

Tight Revenue Gaps among Simple Mechanisms

• Yaonan Jin
• Pinyan Lu
• Zhihao Gavin Tang
• Tao Xiao

We consider a fundamental problem in microeconomics: Selling a single item among a number of buyers whose values are drawn from known independent and regular distributions. There are four widely-used and widely-studied mechanisms in this literature: Anonymous Posted-Pricing (AP), Second-Price Auction with Anonymous Reserve (AR), Sequential Posted-Pricing (SPM), and Myerson Auction (OPT). Myerson Auction is optimal but complicated, which also suffers a few issues in practice such as fairness; AP is the simplest mechanism, but its revenue is also the lowest among these four; AR and SPM are of intermediate complexity and revenue. We study the revenue gaps among these four mechanisms, which is defined as the largest ratio between revenues from two mechanisms. We establish two tight ratios and one tighter bound: 1. SPM/AP. This ratio studies the power of discrimination in pricing schemes. We obtain the tight ratio of roughly 2. 62, closing the previous known bounds [ e /( e – 1), e ]. 2. AR/AP. This ratio studies the relative power of auction vs. pricing schemes, when no discrimination is allowed. We get the tight ratio of π 2 /6 ≈ 1. 64, closing the previous known bounds [ e /( e – 1), e ]. 3. OPT/AR. This ratio studies the power of discrimination in auctions. Previously, the revenue gap is known to be in interval [2, e ], and the lower-bound of 2 is conjectured to be tight [38, 37, 4]. We disprove this conjecture by obtaining a better lower-bound of 2. 15.

SODA Conference 2019 Conference Paper

Zeros of Holant problems: locations and algorithms

• Heng Guo 0001
• Chao Liao
• Pinyan Lu
• Chihao Zhang 0001

We present fully polynomial-time (deterministic or randomised) approximation schemes for Holant problems, defined by a non-negative constraint function satisfying a generalised second order recurrence modulo a couple of exceptional cases. As a consequence, any non-negative Holant problem on cubic graphs has an efficient approximation algorithm unless the problem is equivalent to approximately counting perfect matchings, a central open problem in the area. This is in sharp contrast to the computational phase transition shown by 2-state spin systems on cubic graphs. Our main technique is the recently established connection between zeros of graph polynomials and approximate counting. We also use the “winding” technique to deduce the second result on cubic graphs.

STOC Conference 2018 Conference Paper

Counting hypergraph colourings in the local lemma regime

• Heng Guo 0001
• Chao Liao
• Pinyan Lu
• Chihao Zhang 0001

We give a fully polynomial-time approximation scheme (FPTAS) to count the number of q -colorings for k -uniform hypergraphs with maximum degree Δ if k ≥ 28 and q > 315Δ 14/ k −14 . We also obtain a polynomial-time almost uniform sampler if q >798Δ 16/ k −16/3 . These are the first approximate counting and sampling algorithms in the regime q ≪Δ (for large Δ and k ) without any additional assumptions. Our method is based on the recent work of Moitra (STOC, 2017). One important contribution of ours is to remove the dependency of k and Δ in Moitra’s approach.

SODA Conference 2018 Conference Paper

Dichotomy for Real Holant c Problems

• Jin-Yi Cai
• Pinyan Lu
• Mingji Xia

AAAI Conference 2018 Conference Paper

Facility Location Games With Fractional Preferences

• Chi Kit Ken Fong
• Minming Li
• Pinyan Lu
• Taiki Todo
• Makoto Yokoo

In this paper, we propose a fractional preference model for the facility location game with two facilities that serve the similar purpose on a line where each agent has his location information as well as fractional preference to indicate how well they prefer the facilities. The preference for each facility is in the range of [0, L] such that the sum of the preference for all facilities is equal to 1. The utility is measured by subtracting the sum of the cost of both facilities from the total length L where the cost of facilities is defined as the multiplication of the fractional preference and the distance between the agent and the facilities. We first show that the lower bound for the objective of minimizing total cost is at least Ω(n 1 3 ). Hence, we use the utility function to analyze the agents’ satification. Our objective is to place two facilities on [0, L] to maximize the social utility or the minimum utility. For each objective function, we propose deterministic strategy-proof mechanisms. For the objective of maximizing the social utility, we present an optimal deterministic strategy-proof mechanism in the case where agents can only misreport their locations. In the case where agents can only misreport their preferences, we present a 2approximation deterministic strategy-proof mechanism. Finally, we present a 4-approximation deterministic strategyproof mechanism and a randomized strategy-proof mechanism with an approximation ratio of 2 where agents can misreport both the preference and location information. Moreover, we also give a lower-bound of 1. 06. For the objective of maximizing the minimum utility, we give a lower-bound of 1. 5 and present a 2-approximation deterministic strategyproof mechanism where agents can misreport both the preference and location.

SODA Conference 2018 Conference Paper

Separation in Correlation-Robust Monopolist Problem with Budget

• Nikolai Gravin
• Pinyan Lu

SODA Conference 2018 Conference Paper

The Value of Information Concealment

• Hu Fu 0001
• Christopher Liaw
• Pinyan Lu
• Zhihao Gavin Tang

SODA Conference 2017 Conference Paper

An FPTAS for Counting Proper Four-Colorings on Cubic Graphs

• Pinyan Lu
• Kuan Yang 0001
• Chihao Zhang 0001
• Minshen Zhu

Graph coloring is arguably the most exhaustively studied problem in the area of approximate counting. It is conjectured that there is a fully polynomial-time (randomized) approximation scheme (FPTAS/FPRAS) for counting the number of proper colorings as long as q ≥ Δ + 1, where q is the number of colors and Δ is the maximum degree of the graph. The bound of q = Δ + 1 is the uniqueness threshold for Gibbs measure on Δ-regular infinite trees. However, the conjecture remained open even for any fixed Δ > 3 (The cases of Δ = 1, 2 are trivial). In this paper, we design an FP- TAS for counting the number of proper four-colorings on graphs with maximum degree three and thus confirm the conjecture in the case of Δ = 3. This is the first time to achieve this optimal bound of q = Δ + 1. Previously, the best FPRAS requires and the best deterministic FPTAS requires q > 2. 581Δ + 1 for general graphs. In the case of Δ = 3, the best previous result is an FPRAS for counting proper 5-colorings. We note that there is a barrier to go beyond q = Δ + 2 for single-site Glauber dynamics based FPRAS and we overcome this by correlation decay approach. Moreover, we develop a number of new techniques for the correlation decay approach which can find applications in other approximate counting problems.

SODA Conference 2016 Conference Paper

Canonical Paths for MCMC: from Art to Science

• Lingxiao Huang
• Pinyan Lu
• Chihao Zhang 0001

NeurIPS Conference 2016 Conference Paper

Combinatorial Multi-Armed Bandit with General Reward Functions

• Wei Chen
• Wei Hu
• Fu Li
• Jian Li
• Yu Liu
• Pinyan Lu

In this paper, we study the stochastic combinatorial multi-armed bandit (CMAB) framework that allows a general nonlinear reward function, whose expected value may not depend only on the means of the input random variables but possibly on the entire distributions of these variables. Our framework enables a much larger class of reward functions such as the $\max()$ function and nonlinear utility functions. Existing techniques relying on accurate estimations of the means of random variables, such as the upper confidence bound (UCB) technique, do not work directly on these functions. We propose a new algorithm called stochastically dominant confidence bound (SDCB), which estimates the distributions of underlying random variables and their stochastically dominant confidence bounds. We prove that SDCB can achieve $O(\log T)$ distribution-dependent regret and $\tilde{O}(\sqrt{T})$ distribution-independent regret, where $T$ is the time horizon. We apply our results to the $K$-MAX problem and expected utility maximization problems. In particular, for $K$-MAX, we provide the first polynomial-time approximation scheme (PTAS) for its offline problem, and give the first $\tilde{O}(\sqrt T)$ bound on the $(1-\epsilon)$-approximation regret of its online problem, for any $\epsilon>0$.

STOC Conference 2015 Conference Paper

FPTAS for #BIS with Degree Bounds on One Side

• Jingcheng Liu 0001
• Pinyan Lu

Counting the number of independent sets for a bipartite graph (#BIS) plays a crucial role in the study of approximate counting. It has been conjectured that there is no fully polynomial-time (randomized) approximation scheme (FPTAS/FPRAS) for #BIS, and it was proved that the problem for instances with a maximum degree of 6 is already as hard as the general problem. In this paper, we obtain a surprising tractability result for a family of #BIS instances. We design a very simple deterministic fully polynomial-time approximation scheme (FPTAS) for #BIS when the maximum degree for one side is no larger than 5. There is no restriction for the degrees on the other side, which do not even have to be bounded by a constant. Previously, FPTAS was only known for instances with a maximum degree of 5 for both sides.

SODA Conference 2015 Conference Paper

FPTAS for Counting Monotone CNF

• Jingcheng Liu 0001
• Pinyan Lu

A monotone CNF formula is a Boolean formula in conjunctive normal form where each variable appears positively. We design a deterministic fully polynomial-time approximation scheme (FPTAS) for counting the number of satisfying assignments for a given monotone CNF formula when each variable appears in at most 5 clauses. Equivalently, this is also an FPTAS for counting set covers where each set contains at most 5 elements. If we allow variables to appear in a maximum of 6 clauses (or sets to contain 6 elements), it is NP-hard to approximate it. Thus, this gives a complete understanding of the approximability of counting for monotone CNF formulas. It is also an important step towards a complete characterization of the approximability for all bounded degree Boolean #CSP problems. In addition, we study the hypergraph matching problem, which arises naturally towards a complete classification of bounded degree Boolean #CSP problems, and show an FPTAS for counting 3D matchings of hypergraphs with maximum degree 4. Our main technique is correlation decay, a powerful tool to design deterministic FPTAS for counting problems defined by local constraints among a number of variables. All previous uses of this design technique fall into two categories: each constraint involves at most two variables, such as independent set, coloring, and spin systems in general; or each variable appears in at most two constraints, such as matching, edge cover, and holant problem in general. The CNF problems studied here have more complicated structures than these problems and require new design and proof techniques. As it turns out, the technique we developed for the CNF problem also works for the hypergraph matching problem. We believe that it may also find applications in other CSP or more general counting problems.

SODA Conference 2014 Conference Paper

A Simple FPTAS for Counting Edge Covers

• Chengyu Lin 0001
• Jingcheng Liu 0001
• Pinyan Lu

An edge cover of a graph is a set of edges such that every vertex has at least an adjacent edge in it. We design a very simple deterministic fully polynomial-time approximation scheme (FPTAS) for counting the number of edge covers for any graph. Previously, approximation algorithm is only known for 3 regular graphs and it is randomized [3]. Our main technique is correlation decay, which is a powerful tool to design FPTAS for counting problems. In order to get FPTAS for general graphs without degree bound, we make use of a stronger notion called computationally efficient correlation decay, which was introduced in [19].

TCS Journal 2014 Journal Article

Frontiers in algorithmics

• Pinyan Lu
• Jack Snoeyink

STOC Conference 2014 Conference Paper

Optimal competitive auctions

• Ning Chen 0005
• Nikolai Gravin
• Pinyan Lu

We study the design of truthful auctions for selling identical items in unlimited supply (e.g., digital goods) to n unit demand buyers. This classic problem stands out from profit-maximizing auction design literature as it requires no probabilistic assumptions on buyers' valuations and employs the framework of competitive analysis. Our objective is to optimize the worst-case performance of an auction, measured by the ratio between a given benchmark and revenue generated by the auction.

SODA Conference 2013 Conference Paper

Correlation Decay up to Uniqueness in Spin Systems

• Liang Li
• Pinyan Lu
• Yitong Yin

We give a complete characterization of the two-state anti-ferromagnetic spin systems which exhibit strong spatial mixing on general graphs. We show that a two-state anti-ferromagnetic spin system exhibits strong spatial mixing on all graphs of maximum degree at most Δ if and only if the system has a unique Gibbs measure on infinite regular trees of degree up to Δ, where Δ can be either bounded or unbounded. As a consequence, there exists an FPTAS for the partition function of a two-state anti-ferromagnetic spin system on graphs of maximum degree at most Δ when the uniqueness condition is satisfied on infinite regular trees of degree up to Δ. In particular, an FPTAS exists for arbitrary graphs if the uniqueness is satisfied on all infinite regular trees. This covers as special cases all previous algorithmic results for two-state anti-ferromagnetic systems on general-structure graphs. Combining with the FPRAS for two-state ferromagnetic spin systems of Jerrum-Sinclair and Goldberg-Jerrum-Paterson, and the very recent hardness results of Sly-Sun and independently of Galanis-Štefankovič-Vigoda, this gives a complete classification, except at the phase transition boundary, of the approximability of all two-state spin systems, on either degree-bounded families of graphs or family of all graphs.

SODA Conference 2013 Conference Paper

Dichotomy for Holant* Problems with Domain Size 3

• Jin-Yi Cai
• Pinyan Lu
• Mingji Xia

SODA Conference 2012 Conference Paper

Approximate counting via correlation decay in spin systems

• Liang Li
• Pinyan Lu
• Yitong Yin

STOC Conference 2012 Conference Paper

Budget feasible mechanism design: from prior-free to bayesian

• Xiaohui Bei
• Ning Chen 0005
• Nikolai Gravin
• Pinyan Lu

Budget feasible mechanism design studies procurement combinatorial auctions in which the sellers have private costs to produce items, and the buyer (auctioneer) aims to maximize a social valuation function on subsets of items, under the budget constraint on the total payment. One of the most important questions in the field is "which valuation domains admit truthful budget feasible mechanisms with 'small' approximations (compared to the social optimum)?" Singer [35] showed that additive and submodular functions have a constant approximation mechanism. Recently, Dobzinski, Papadimitriou, and Singer [20] gave an O(log 2 n) approximation mechanism for subadditive functions; further, they remarked that: "A fundamental question is whether, regardless of computational constraints, a constant-factor budget feasible mechanism exists for subadditive functions." In this paper, we address this question from two viewpoints: prior-free worst case analysis and Bayesian analysis, which are two standard approaches from computer science and economics, respectively. - For the prior-free framework, we use a linear program (LP) that describes the fractional cover of the valuation function; the LP is also connected to the concept of approximate core in cooperative game theory. We provide a mechanism for subadditive functions whose approximation is O(I), via the worst case integrality gap I of this LP. This implies an O(log n)-approximation for subadditive valuations, O(1)-approximation for XOS valuations, as well as for valuations having a constant integrality gap. XOS valuations are an important class of functions and lie between the submodular and the subadditive classes of valuations. We further give another polynomial time O(log n/(log log n)) sub-logarithmic approximation mechanism for subadditive functions. Both of our mechanisms improve the best known approximation ratio O(log 2 n). - For the Bayesian framework, we provide a constant approximation mechanism for all subadditive functions, using the above prior-free mechanism for XOS valuations as a subroutine. Our mechanism allows correlations in the distribution of private information and is universally truthful.

AAAI Conference 2012 Conference Paper

Computing the Nucleolus of Matching, Cover and Clique Games

• Ning Chen
• Pinyan Lu
• Hongyang Zhang

In cooperative games, a key question is to find a division of payoffs to coalition members in a fair manner. Nucleolus is one of such solution concepts that provides a stable solution for the grand coalition. We study the computation of the nucleolus of a number of cooperative games, including fractional matching games and fractional edge cover games on general weighted graphs, as well as vertex cover games and clique games on weighted bipartite graphs. Our results are on the positive side—we give efficient algorithms to compute the nucleolus, as well as the least core, of all of these games.

TCS Journal 2011 Journal Article

A computational proof of complexity of some restricted counting problems

• Jin-Yi Cai
• Pinyan Lu
• Mingji Xia

We explore a computational approach to proving the intractability of certain counting problems. These problems can be described in various ways, and they include concrete problems such as counting the number of vertex covers or independent sets for 3-regular graphs. The high level principle of our approach is algebraic, which provides sufficient conditions for interpolation to succeed. Another algebraic component is holographic reductions. We then analyze in detail polynomial maps on R 2 induced by some combinatorial constructions. These maps define sufficiently complicated dynamics of R 2 that we can only analyze them computationally. In this paper we use both numerical computation (as intuitive guidance) and symbolic computation (as proof theoretic verification) to derive that a certain collection of combinatorial constructions, in myriad combinations, fulfills the algebraic requirements of proving #P-hardness. The final result is a dichotomy theorem for a class of counting problems. This includes a class of generic holant problems with an arbitrary real valued edge signature over ( 2, 3 ) -regular undirected graphs. In particular, it includes all partition functions with 0–1 vertex assignments and an arbitrary real valued edge function over all 3-regular undirected graphs.

SODA Conference 2011 Conference Paper

Dichotomy for Holant* Problems of Boolean Domain

• Jin-Yi Cai
• Pinyan Lu
• Mingji Xia

Holant problems are a general framework to study counting problems. Both counting Constraint Satisfaction Problems (#CSP) and graph homomorphisms are special cases. We prove a complexity dichotomy theorem for Holant*( F ), where F is a set of constraint functions on Boolean variables and output complex values. The constraint functions need not be symmetric functions. We identify four classes of problems which are polynomial time computable; all other problems are proved to be #P-hard. The main proof technique and indeed the formulation of the theorem use holographic algorithms and reductions. By considering these counting problems over the complex domain, we discover surprising new tractable classes, which are associated with isotropic vectors, i. e. , a (non-zero) vector whose inner product with itself is zero.

SODA Conference 2011 Conference Paper

On the Approximability of Budget Feasible Mechanisms

• Ning Chen 0005
• Nikolai Gravin
• Pinyan Lu

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 monotone submodular functions: We give a randomized mechanism with an approximation ratio of 7. 91 (improving on the previous best-known result 233. 83), and a deterministic mechanism with an approximation ratio of 8. 34. We also study the knapsack problem, which is a special submodular function, give a 2 + √2 approximation deterministic mechanism (improving on the previous best-known result 5), and a 3 approximation randomized mechanism. We provide similar results for an extended knapsack problem with heterogeneous items, where items are divided into groups and one can pick at most one item from each group. Finally we show a lower bound of 1 + √2 for the approximation ratio of deterministic mechanisms and 2 for randomized mechanisms for knapsack, as well as the general monotone submodular functions. Our lower bounds are unconditional, and do not rely on any computational or complexity assumptions.

FOCS Conference 2010 Conference Paper

Holographic Algorithms with Matchgates Capture Precisely Tractable Planar_#CSP

• Jin-Yi Cai
• Pinyan Lu
• Mingji Xia

Valiant introduced match gate 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, match gate 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. More precisely, we prove complexity dichotomy theorems in the framework of counting CSP problems. The local constraint functions take Boolean inputs, and can be arbitrary real-valued symmetric functions. We prove that, every problem in this class belongs to precisely three categories: (1) those which are tractable (i. e. , polynomial time computable) on general graphs, or (2) those which are #P-hard on general graphs but ractable on planar graphs, or (3) those which are #P-hard even on planar graphs. The classification criteria are explicit. Moreover, problems in category (2) are tractable on planar graphs precisely by holographic algorithms with matchgates.

TCS Journal 2010 Journal Article

On blockwise symmetric signatures for matchgates

• Jin-Yi Cai
• Pinyan Lu

We give a classification of blockwise symmetric signatures in the theory of matchgate computations. The main proof technique uses matchgate identities, also known as useful Grassmann–Plücker identities.

STOC Conference 2009 Conference Paper

Holant problems and counting CSP

• Jin-Yi Cai
• Pinyan Lu
• Mingji Xia

We propose and explore a novel alternative framework to study the complexity of counting problems, called Holant Problems. Compared to counting Constrained Satisfaction Problems (CSP), it is a refinement with a more explicit role for the function constraints. Both graph homomorphism and CSP can be viewed as special cases of Holant Problems. We prove complexity dichotomy theorems in this framework. Because the framework is more stringent, previous dichotomy theorems for CSP problems no longer apply. Indeed, we discover surprising tractable subclasses of counting problems, which could not have been easily specified in the CSP framework. The main technical tool we use and develop is holographic reductions. Another technical tool used in combination with holographic reductions is polynomial interpolations. The study of Holant Problems led us to discover and prove a complexity dichotomy theorem for the most general form of Boolean CSP where every constraint function takes values in the complex number field {C}.

TCS Journal 2009 Journal Article

Holographic algorithms: The power of dimensionality resolved

• Jin-Yi Cai
• Pinyan Lu

Valiant’s theory of holographic algorithms is a novel methodology to achieve exponential speed-ups in computation. A fundamental parameter in holographic algorithms is the dimension of the linear basis vectors. We completely resolve the problem of the power of higher dimensional bases. We prove that 2-dimensional bases are universal for holographic algorithms.

FOCS Conference 2008 Conference Paper

Holographic Algorithms by Fibonacci Gates and Holographic Reductions for Hardness

• Jin-Yi Cai
• Pinyan Lu
• Mingji Xia

We propose a new method to prove complexity dichotomy theorems. First we introduce Fibonacci gates which provide a new class of polynomial time holographic algorithms. Then we develop holographic reductions. We show that holographic reductions followed by interpolations provide a uniform strategy to prove #P-hardness.

SODA Conference 2008 Conference Paper

Holographic algorithms with unsymmetric signatures

• Jin-Yi Cai
• Pinyan Lu

STOC Conference 2007 Conference Paper

Holographic algorithms: from art to science

• Jin-Yi Cai
• Pinyan Lu

We develop the theory of holographic algorithms. We definea basis manifold and give characterizations of algebraic varieties of realizable symmetric generators and recognizers on this manifold. We present a polynomial time decision algorithm for the simultaneous realizability problem. Using the general machinery we are able to giveunexpected holographic algorithms for some counting problems, modulo certain Mersenne type integers. These counting problems are P-complete without the moduli. Going beyond symmetric signatures, we define d -admissibility and d -realizability for general signatures, and give a characterizationof 2-admissibility.