Process supervision has emerged as a promising approach for enhancing LLM reasoning, yet existing methods fail to distinguish meaningful progress from mere verbosity, leading to limited reasoning capabilities and unresolved token inefficiency.To address this, we propose Stage-aware Hierarchical Advantage via Potential Estimation (SHAPE), a framework that formalizes reasoning as a trajectory through a state space of empirical solvability.SHAPE introduces a hierarchical credit assignment mechanism: at the segment level, it employs a stageaware advantage function to prioritize efficient breakthroughs in low-potential states; at the token level, it utilizes entropy-driven redistribution to sharpen execution signals.Extensive experiments in math reasoning across three base models and five benchmarks demonstrate that SHAPE achieves an average accuracy gain of 3% with 30% reduced token consumption.

We examine fixed-price mechanisms in bilateral trade through the lens of regret minimization. Our main results are twofold. (i) For independent values, a near-optimal $\widetildeΘ(T^{2/3})$ tight bound for $\textsf{Global Budget Balance}$ fixed-price mechanisms with two-bit/one-bit feedback. (ii) For correlated/adversarial values, a near-optimal $Ω(T^{3/4})$ lower bound for $\textsf{Global Budget Balance}$ fixed-price mechanisms with two-bit/one-bit feedback, which improves the best known $Ω(T^{5/7})$ lower bound obtained in the work [BCCF24] and, up to polylogarithmic factors, matches the $\widetilde{\mathcal{O}}(T^{3 / 4})$ upper bound obtained in the same work. Our work in combination with the previous works [CCCFL24mor, CCCFL24jmlr, AFF24, BCCF24] (essentially) gives a thorough understanding of regret minimization for fixed-price bilateral trade. En route, we have developed two technical ingredients that might be of independent interest: (i) A novel algorithmic paradigm, called $\textit{fractal elimination}$, to address one-bit feedback and independent values. (ii) A new $\textit{lower-bound construction}$ with novel proof techniques, to address the $\textsf{Global Budget Balance}$ constraint and correlated values.

We propose the first local search algorithm for Euclidean clustering that attains an \(O(1)\)-approximation in almost-linear time. Specifically, for Euclidean \(k\)-Means, our algorithm achieves an \(O(c)\)-approximation in \(\tilde O(n^{1+1/c})\) time, for any constant \(c \ge 1\), maintaining the same running time as the previous (non-local-search-based) approach [la Tour and Saulpic, arXiv’2407.11217] while improving the approximation factor from \(O(c^6)\) to \(O(c)\). The algorithm generalizes to any metric space with sparse spanners, delivering efficient constant approximation in \(\ell_p\) metrics, doubling metrics, Jaccard metrics, etc.

Real-world pricing mechanisms are typically optimized using training data, a setting corresponding to the pricing query complexity problem in Mechanism Design. The previous work [11] studies the single-distribution case1, with tight bounds of ~Θ (ε-3 ) for a general distribution and ~Θ (ε-2 ) for either a regular or monotone-hazard-rate (MHR) distribution, where ε ∈ (0, 1) denotes the (additive) revenue loss of a learned uniform price relative to the Bayesian-optimal uniform price.

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.

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.

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.

Designing small-sized coresets, which approximately preserve the costs of the solutions for large datasets, has been an important research direction for the past decade. We consider coreset construction for a variety of general constrained clustering problems. We introduce a general class of assignment constraints, including capacity constraints on cluster centers, and assignment structure constraints for data points (modeled by a convex body B ). We give coresets for clustering problems with such general assignment constraints that significantly generalize and improve known results. Notable implications include the first ε-coreset for capacitated and fair k-MEDIAN with m outliers in Euclidean spaces whose size is Õ (m + k2ε-4), generalizing and improving upon the prior bounds in [BCJ+ 22, HJLW23] (for capacitated k-MEDIAN, the coreset size bound obtained in [BCJ+22] is Õ (k3ε-6), and for k-MEDIAN with m outliers, the coreset size bound obtained in [HJLW23] is Õ (m + k3ε-5)), and the first ε-coreset of size poly(kε-1) for fault-tolerant clustering for various types of metric spaces.

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.

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.

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.

The classical prophet inequalities problem introduced by Krengel and Sucheston [1977, 1978] assumed complete knowledge of distributions. However, such an assumption may be unrealistic both in practice and for some applications.

The competitive auction was first proposed by Goldberg, Hartline, and Wright. In their paper [Goldberg et al, 2001], they introduce the competitive analysis framework of online algorithm design into the traditional revenue-maximizing auction design problem. While the competitive analysis framework only cares about the worst-case bound, a growing body of work in the online algorithm community studies the learning-augmented framework. In this framework, designers are allowed to leverage imperfect machine-learned predictions of unknown information and pursue better theoretical guarantees when the prediction is accurate(consistency). Meanwhile, designers also need to maintain a nearly-optimal worst-case ratio(robustness).

This paper proves the tight sample complexity of Second-Price Auction with Anonymous Reserve, up to a logarithmic factor, for each of all the value distribution families studied in the literature: [0,1]-bounded, [1,H]-bounded, regular, and monotone hazard rate (MHR). Remarkably, the setting-specific tight sample complexity poly(ε^{-1}) depends on the precision ε ∈ (0, 1), but not on the number of bidders n ≥ 1. Further, in the two bounded-support settings, our learning algorithm allows correlated value distributions. In contrast, the tight sample complexity Θ̃(n) ⋅ poly(ε^{-1}) of Myerson Auction proved by Guo, Huang and Zhang (STOC 2019) has a nearly-linear dependence on n ≥ 1, and holds only for independent value distributions in every setting. We follow a similar framework as the Guo-Huang-Zhang work, but replace their information theoretical arguments with a direct proof.

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.

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/e2 ≈ 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

We prove that the PoA of First Price Auctions is 1-1/ e 2 ≈ 0.8647, closing the gap between the best known bounds [0.7430, 0.8689].

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].

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.

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.

Negative pairs, especially hard negatives as combined with common negatives (easy to discriminate), are essential in contrastive learning, which plays a role of avoiding degenerate solutions in the sense of constant representation across different instances. Inspired by recent hard negative mining methods via pairwise mixup operation in vision, we propose M-Mix, which dynamically generates a sequence of hard negatives. Compared with previous methods, M-Mix mainly has three features: 1) adaptively choose samples to mix; 2) simultaneously mix multiple samples; 3) automatically assign different mixing weights to the selected samples. We evaluate our method on two image datasets (CIFAR-10, CIFAR-100), five node classification datasets (PPI, DBLP, Pubmed, etc), five graph classification datasets (IMDB, PTC_MR, etc), and two downstream combinatorial tasks (graph edit distance and node clustering). Results show that it achieves state-of-the-art performance under self-supervised settings. Code is available at: https://github.com/Sherrylone/m-mix.

Abstract. This paper considers Bayesian revenue maximization in the [Formula: see text]-unit setting, where a monopolist seller has [Formula: see text] copies of an indivisible item and faces [Formula: see text] unit-demand buyers (whose value distributions can be nonidentical). Four basic mechanisms among others have been widely employed in practice and widely studied in the literature: Myerson auction, sequential posted-pricing, [Formula: see text]-th price auction with anonymous reserve, and anonymous pricing. Regarding a pair of mechanisms, we investigate the largest possible ratio between the two revenues (also known as the revenue gap), over all possible value distributions of the buyers. Divide these four mechanisms into two groups: (i) the discriminating mechanism group, Myerson auction and sequential posted-pricing, and (ii) the anonymous mechanism group, anonymous reserve and anonymous pricing. Within one group, the involved two mechanisms have an asymptotically tight revenue gap of [Formula: see text]. In contrast, any two mechanisms from the different groups have an asymptotically tight revenue gap of [Formula: see text].

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.

We consider the problem of fairly dividing m indivisible chores among n agents. The fairness measure we consider here is the maximin share. The previous best known result is that there always exists a 4/3-approximation maximin share allocation[3]. With our algorithm, we can always find a 11/9-approximation maximin share allocation for any instance. We also discuss how to improve the efficiency of the algorithm and its connection to the job scheduling problem. The full paper can be found at https://arxiv.org/abs/1907.04505.

This paper considers Bayesian revenue maximization in the k-unit setting, where a monopolist seller has k copies of an indivisible item and faces n unit-demand buyers (whose value distributions can be non-identical). Four basic mechanisms among others have been widely employed in practice and widely studied in the literature: Myerson Auction, Sequential Posted-Pricing, (k + 1)-th Price Auction with Anonymous Reserve, and Anonymous Pricing. Regarding a pair of mechanisms, we investigate the largest possible ratio between the two revenues (a.k.a. the revenue gap), over all possible value distributions of the buyers. Divide these four mechanisms into two groups: (i) the discriminating mechanism group, Myerson Auction and Sequential Posted-Pricing, and (ii) the anonymous mechanism group, Anonymous Reserve and Anonymous Pricing. Within one group, the involved two mechanisms have an asymptotically tight revenue gap of 1 + Θ(1 / √k). In contrast, any two mechanisms from the different groups have an asymptotically tight revenue gap of Θ(łog k).

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].

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.

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.

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 in 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 two-state spin systems on cubic graphs. Our main technique is the recently established connection between zeros of graph polynomials and approximate counting.

We initiate a study of the classification of approximation complexity of the eight-vertex model defined over 4-regular graphs. The eight-vertex model, together with its special case the six-vertex model, is one of the most extensively studied models in statistical physics, and can be stated as a problem of counting weighted orientations in graph theory. Our result concerns the approximability of the partition function on all 4-regular graphs, classified according to the parameters of the model. Our complexity results conform to the phase transition phenomenon from physics. We introduce a quantum decomposition of the eight-vertex model and prove a set of closure properties in various regions of the parameter space. Furthermore, we show that there are extra closure properties on 4-regular planar graphs. These regions of the parameter space are concordant with the phase transition threshold. Using these closure properties, we derive polynomial time approximation algorithms via Markov chain Monte Carlo. We also show that the eight-vertex model is NP-hard to approximate on the other side of the phase transition threshold.

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.

We study zeros of the partition functions of ferromagnetic 2-state spin systems in terms of the external field, and obtain new zero-free regions of these systems via a refinement of Asano's and Ruelle's contraction method. The strength of our results is that they do not depend on the maximum degree of the underlying graph. Via Barvinok's method, we also obtain new efficient and deterministic approximate counting algorithms. When the edge interaction is attractive for both spins, our algorithm outperforms all other methods such as Markov chain Monte Carlo and correlation decay.

We consider a fundamental problem in microeconomics: selling a single item to a number of potential buyers, whose values are drawn from known independent and regular (not necessarily identical) distributions. There are four widely used and widely studied mechanisms in the literature: Myerson Auction (OPT), Sequential Posted-Pricing (SPM), Second-Price Auction with Anonymous Reserve (AR), and Anonymous Pricing (AP). OPT is revenue-optimal but complicated and also experiences several issues in practice such as fairness; AP is the simplest mechanism but also generates the lowest revenue among these four mechanisms; SPM and AR are of intermediate complexity and revenue. We explore revenue gaps among these mechanisms, each of which is defined as the largest ratio between revenues from a pair of mechanisms. We establish two tight bounds and one tighter bound: 1. SPM vs. AP: this ratio studies the power of discrimination in pricing schemes. We obtain the tight ratio of constant ${\cal{C}}^* \approx {2.62}$, closing the gap between $[\frac{e}{e - 1}, e]$ left before. 2. AR vs. AP: this ratio measures the relative power of auction scheme vs. pricing scheme, when no discrimination is allowed. We attain the tight ratio of $\frac{\pi^2}{6} \approx 1.64$, closing the previously known bounds $[\frac{e}{e - 1}, e]$. 3. OPT vs. AR: this ratio quantifies the power of discrimination in auction schemes and is previously known to be somewhere between [2, e]. The lower bound of 2 was conjectured to be tight by Hartline and Roughgarden [ Proceedings of the 10th ACM Conference on Electronic Commerce, 2009, pp. 225--234] and Alaei et al. [ Games Econom. Behav., 118 (2019), pp. 494--510]. We acquire a better lower bound of 2.15 and thus disprove this conjecture.

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 PlackettLuce model increases.

We give a fully polynomial-time approximation scheme (FPTAS) to count the number of independent sets on almost every $Δ$-regular bipartite graph if $Δ\ge 53$. In the weighted case, for all sufficiently large integers $Δ$ and weight parameters $λ=\tildeΩ\left(\frac{1}Δ\right)$, we also obtain an FPTAS on almost every $Δ$-regular bipartite graph. Our technique is based on the recent work of Jenssen, Keevash and Perkins (SODA, 2019) and we also apply it to confirm an open question raised there: For all $q\ge 3$ and sufficiently large integers $Δ=Δ(q)$, there is an FPTAS to count the number of $q$-colorings on almost every $Δ$-regular bipartite graph.

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.

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.

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).

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.

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.

We give a fully polynomial-time approximation scheme (FPTAS) to count the number of $q$-colorings for $k$-uniform hypergraphs with maximum degree $\Delta$ if $k\ge 28$ and $q > 357 \Delta^{\frac{14}{k-14}}$. We also obtain a polynomial-time almost uniform sampler if $q>931 \Delta^{\frac{16}{k-16/3}}$. These are the first approximate counting and sampling algorithms in the regime $q\ll\Delta$ (for large $\Delta$ 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 $\Delta$ in Moitra's approach.

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 2-approximation deterministic strategy-proof mechanism. Finally, we present a 4-approximation deterministic strategy-proof 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 strategy-proof mechanism where agents can misreport both the preference and location.

Generating good revenue is one of the most important problems in Bayesian auction design, and many (approximately) optimal dominant-strategy incentive compatible (DSIC) Bayesian mechanisms have been constructed for various auction settings. However, most existing studies do not consider the complexity for the seller to carry out the mechanism. It is assumed that the seller knows "each single bit" of the distributions and is able to optimize perfectly based on the entire distributions. Unfortunately this is a strong assumption and may not hold in reality: for example, when the value 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. We only allow the seller to have limited oracle accesses to the players' value distributions, via quantile queries and value queries. For a large class of auction settings, we prove logarithmic lower-bounds for the query complexity for any DSIC Bayesian mechanism to be of any constant approximation to the optimal revenue. For single-item auctions and multi-item auctions with unit-demand or additive valuation functions, we prove tight upper-bounds via efficient query schemes, without requiring the distributions to be regular or have monotone hazard rate. Thus, in those auction settings the seller needs to access much less than the full distributions in order to achieve approximately optimal revenue.

Holant problems capture a class of Sum-of-Product computations such as counting matchings. It is inspired by holographic algorithms and is equivalent to tensor networks, with counting CSP being a special case. A complexity classification for Holant problems is more difficult to prove, not only because it logically implies a classification for counting CSP, but also due to the deeper reason that there exist more intricate polynomial time tractable problems in the broader framework. We discover a new family of constraint functions ℒ which define polynomial time computable counting problems. These do not appear in counting CSP, and no newly discovered tractable constraints can be symmetric. It has a delicate support structure related to error-correcting codes. Local holographic transformations is fundamental in its tractability. We prove a complexity dichotomy theorem for all Holant problems defined by any real valued constraint function set on Boolean variables and contains two 0–1 pinning functions. Previously, dichotomy for the same framework was only known for symmetric constraint functions. The set ℒ supplies the last piece of tractability. We also prove a dichotomy for a variant of counting CSP as a technical component toward this Holant dichotomy.

We consider a revenue optimizing seller selling a single item to a buyer, on whose private value the seller has a noisy signal. We show that, when the signal is kept private, arbitrarily more revenue could potentially be extracted than if the signal is leaked or revealed. We then show that, if the seller is not allowed to make payments to the buyer and if the value distribution conditioning on each signal is regular, the gap between the two is bounded by a multiplicative factor of 3. We give examples showing that both conditions are necessary for a constant bound on the gap to hold. We connect this scenario to multi-bidder single-item auctions where bidders’ values are correlated. Similarly to the setting above, we show that the revenue of a Bayesian incentive compatible, ex post individually rational auction can be arbitrarily larger than that of a dominant strategy incentive compatible auction, whereas the two are no more than a factor of 5 apart if the auctioneer never pays the bidders and if the distribution is jointly regular. The upper bounds in both settings degrade gracefully when the distribution is a mixture of a small number of regular distributions.

We consider a monopolist seller that has n heterogeneous items to sell to a single buyer. The seller's goal is to maximize her revenue. We study this problem in the correlation-robust framework recently proposed by Carroll [Econometrica 2017]. In this framework, the seller only knows marginal distributions for each separate item but has no information about correlation across different items in the joint distribution. Any mechanism is then evaluated according to its expected profit in the worst-case, over all possible joint distributions with given marginal distributions. Carroll's main result states that in multi-item monopoly problem with buyer, whose value for a set of items is additive, the optimal correlation-robust mechanism should sell items separately. We use alternative dual Linear Programming formulation for the optimal correlation-robust mechanism design problem. This LP can be used to compute optimal mechanisms in general settings. We give an alternative proof for the additive monopoly problem without constructing worst-case distribution. As a surprising byproduct of our approach we get that separation result continues to hold even when buyer has a budget constraint on her total payment. Namely, the optimal robust mechanism splits the total budget in a fixed way across different items independent of the bids, and then sells each item separately with a respective per item budget constraint.

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.

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.

Budget feasible mechanism design is the study of procurement combinatorial auctions in which the sellers have private costs to produce items, and the buyer (auctioneer) aims to maximize her valuation function on a subset of purchased 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 to the social optimum?” Singer [ Proceedings of the 51st FOCS, IEEE Press, Piscataway, NJ, 2010, pp. 765--774] showed that submodular functions have a constant approximation mechanism. Dobzinski, Papadimitriou, and Singer [ Proceedings of the 12 th ACM Conference on Electronic Commerce, ACM, New York, 2011, pp. 273--282] gave an $O(\log^2n)$ approximation mechanism for subadditive functions and 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 give an affirmative answer to this question. To this end we relax the prior-free mechanism design framework to the Bayesian mechanism design framework (these are two standard approaches from computer science and economics, respectively). Then we convert our results in the Bayesian setting back to the prior-free framework by employing Yao's minimax principle. Along the way, we obtain the following results: (i) a polynomial time constant approximation for XOS valuations (a.k.a. fractionally subadditive valuations, a superset of submodular functions), (ii) a polynomial time $O(\log n / \log \log n)$-approximation for general subadditive valuations, (iii) a constant approximation for general subadditive functions in the Bayesian framework---we allow correlation in the distribution of sellers' costs and provide a universally truthful mechanism, (iv) the existence of a prior-free constant approximation mechanism via Yao's minimax principle.

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 the 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 tractable 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.

For anti-ferromagnetic 2-spin systems, a beautiful connection has been established, namely that the following three notions align perfectly: the uniqueness of Gibbs measures in infinite regular trees, the decay of correlations (also known as spatial mixing), and the approximability of the partition function. The uniqueness condition implies spatial mixing, and an FPTAS for the partition function exists based on spatial mixing. On the other hand, non-uniqueness implies some long range correlation, based on which NP-hardness reductions are built. These connections for ferromagnetic 2-spin systems are much less clear, despite their similarities to anti-ferromagnetic systems. The celebrated Jerrum-Sinclair Markov chain [JS93] works even if spatial mixing fails. Also, for a fixed degree the uniqueness condition is non-monotone with respect to the external field, which seems to have no meaningful interpretation in terms of computational complexity. However, it is still intriguing whether there are some relationship underneath the apparent disparities among them. We provide some answers to this question. Let ; be the (0; 0) and (1; 1) edge interactions respectively ( > 1), and the external field for spin “0”. For graphs with degree bound Δ Δc + 1 where Δc = p p +1 -1 , regardless of the field (even inconsistent fields are allowed), correlation decay always holds and FPTAS exists. If all fields satisfy < c (assuming ), where c = ( =) Δc+1 2 , then a weaker version of spatial mixing holds in all trees. Moreover, if 1, then < c is sufficient to guarantee strong spatial mixing and FPTAS. This improves the best previous algorithm, a Markov chain based FPRAS for = [LLZ14]. The bound c is almost optimal and can be viewed as a variant of the uniqueness condition with the degree d relaxed to be a real number instead of an integer. When 1, uniqueness holds in all infinite regular trees, if and only if int c , where int c = ( =) ⌈Δc⌉+1 2 . If we allow fields > int c ′, where int c ′ = ( =) ⌊Δc⌋+2 2 , then approximating the partition function is #BIS-hard. Interestingly, unless Δc is an integer, neither c nor int c is the tight bound in each own respect. We provide examples where correlation decay continues to hold in a small interval beyond c, and irregular trees in which spatial mixing fails for some < int c .

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$.

Markov Chain Monte Carlo (MCMC) method is a widely used algorithm design scheme with many applications. To make efficient use of this method, the key step is to prove that the Markov chain is rapid mixing. Canonical paths is one of the two main tools to prove rapid mixing. However, there are much fewer success examples comparing to coupling, the other main tool. The main reason is that there is no systematic approach or general recipe to design canonical paths. Building up on a previous exploration by McQuillan [18], we develop a general theory to design canonical paths for MCMC: We reduce the task of designing canonical paths to solving a set of linear equations, which can be automatically done even by a machine. Making use of this general approach, we obtain fully polynomial-time randomized approximation schemes (FPRAS) for counting the number of b-matching with b ≤ 7 and b-edge-cover with b ≤ 2. They are natural generalizations of matchings and edge covers for graphs. No polynomial time approximation was previously known for these problems.

Hardcore and Ising models are two most important families of two state spin systems in statistic physics. Partition function of spin systems is the center concept in statistic physics which connects microscopic particles and their interactions with their macroscopic and statistical properties of materials such as energy, entropy, ferromagnetism, etc. If each local interaction of the system involves only two particles, the system can be described by a graph. In this case, fully polynomial-time approximation scheme (FPTAS) for computing the partition function of both hardcore and anti-ferromagnetic Ising model was designed up to the uniqueness condition of the system. These result are the best possible since approximately computing the partition function beyond this threshold is NP-hard. In this paper, we generalize these results to general physics systems, where each local interaction may involves multiple particles. Such systems are described by hypergraphs. For hardcore model, we also provide FPTAS up to the uniqueness condition, and for anti-ferromagnetic Ising model, we obtain FPTAS under a slightly stronger condition.

We prove a complexity dichotomy theorem for counting constraint satisfaction problems (#CSPs) with nonnegative and algebraic weights. This caps a long series of important results on counting problems including counting unweighted and weighted graph homomorphisms and the celebrated dichotomy theorem for unweighted #CSPs. Our dichotomy theorem gives a succinct criterion for tractability. If a set $\mathcal{F}$ of constraint functions satisfies this criterion, then the problem #CSP$(\mathcal{F})$ defined by $\mathcal{F}$ is solvable in polynomial time; if $\mathcal{F}$ does not satisfy this criterion, then the problem is #P-hard. Furthermore, we show that the question of whether a given $\mathcal{F}$ satisfies the criterion or not is decidable in NP. Surprisingly, our tractability criterion is simpler than the previous criteria for the more restricted classes of counting problems, although when specialized to those classes, they are logically equivalent. Our proof mainly uses linear algebra and represents a departure from universal algebra, the dominant methodology in recent years for the study of #CSPs on large domains.

We propose a uniform approach for the design and analysis of prior-free competitive auctions and online auctions. Our philosophy is to view the benchmark function as a variable parameter of the model and study a broad class of functions instead of a individual target benchmark. We consider a multitude of well-studied auction settings, and improve upon a few previous results. Multi-unit auctions. Given a β-competitive unlimited supply auction, the best previously known multi-unit auction is 2β-competitive. We design a (1+β)-competitive auction reducing the ratio from 4.84 to 3.24. These results carry over to matroid and position auctions. General downward-closed environments. We design a 6.5-competitive auction improving upon the ratio of 7.5. Our auction is noticeably simpler than the previous best one. Unlimited supply online auctions. Our analysis yields an auction with a competitive ratio of 4.12, which significantly narrows the margin of [4, 4.84] previously known for this problem.

We study the efficiency guarantees in the simple auction environment where the auctioneer has one unit of divisible good to be distributed among a number of budget constrained agents. With budget constraints, the social welfare cannot be approximated by a better factor than the number of agents by any truthful mechanism. Thus, we follow a recent work by Dobzinski and Leme[Dobzinski and Leme 2014] to approximate the liquid welfare, which is the welfare of the agents each capped by her/his own budget. We design a new truthful auction with an approximation ratio of √5+1/2 ~1.618, improving the best previous ratio of 2 when the budgets for agents are public knowledge and their valuation is linear (additive). In private budget setting, we propose the first constant approximation auction with approximation ratio of 34. Moreover, this auction works for any valuation function. Previously, only O(log n) approximation was known for linear and decreasing marginal (concave) valuations, and O(log2 n) approximation was known for sub-additive valuations.

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.

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.

We study the approximability of computing the partition function for ferromagnetic two-state spin systems. The remarkable algorithm by Jerrum and Sinclair showed that there is a fully polynomial-time randomized approximation scheme (FPRAS) for the special ferromagnetic Ising model with any given uniform external field. Later, Goldberg and Jerrum proved that it is #BIS-hard for Ising model if we allow inconsistent external fields on different nodes. In contrast to these two results, we prove that for any ferromagnetic two-state spin systems except the Ising model, there exists a threshold for external fields beyond which the problem is #BIS-hard, even if the external field is uniform.

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].

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.

While there is a large and growing body of literature on differentially private mechanisms for answering various classes of queries, to the best of our knowledge "count-range" queries have not been studied. These are a natural class of queries that ask "is the number of rows in a relation satisfying a given predicate between two integers θ1 and θ2?" Such queries can be viewed as a simple form of SQL "having" queries. We begin by developing a provably optimal differentially private mechansim for count-range queries for a single consumer. For count queries (in contrast to countrange queries), Ghosh et al. [9] have provided a differentially private mechanism that simultaneously maximizes utility for multiple consumers. This raises the question of whether such a mechanism exists for count-range queries. We prove that the answer is no --- for count range queries, no such mechanism exists. However, perhaps surprisingly, we prove that such a mechanism does exist for "threshold" queries, which are simply count-range queries for which either θ1 = 0 or θ2 = +∞. Furthermore, we prove that this mechanism is a two-approximation for general count-range queries.

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. In this paper, we give the first dichotomy theorem for Holant problems for domain size greater than two. We discover unexpected tractable families of counting problems, by giving new polynomial time algorithms. This paper also initiates holographic reductions in domains of size greater than two. 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.

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.

We study the complexity of approximation for a weighted counting constraint satisfaction problem #CSP(F). In the conservative case, where F contains all unary functions, a classification is known for the Boolean domain. We give a classification for problems with general finite domain. We define weak log-modularity and weak log-supermodularity, and show that #CSP(F) is in FP if F is weakly log-modular. Otherwise, it is at least as hard to approximate as #BIS, counting independent sets in bipartite graphs, which is believed to be intractable. We further sub-divide the #BIS-hard case. If F is weakly log-supermodular, we show that #CSP(F) is as easy as Boolean log-supermodular weighted #CSP. Otherwise, it is NP-hard to approximate. Finally, we give a trichotomy for the arity-2 case. Then, #CSP(F) is in FP, is #BIS-equivalent, or is equivalent to #SAT, the problem of approximately counting satisfying assignments of a CNF Boolean formula.

Each symmetric matrix $\mathbf{A}$ over $\mathbb{C}$ defines a graph homomorphism function $Z_{\bf A}(\cdot)$ on undirected graphs. The function $Z_{\mathbf{A}} (\cdot)$ is also called the partition function from statistical physics, and can encode many interesting graph properties, including counting vertex covers and $k$-colorings. We study the computational complexity of $Z_{\mathbf{A}} (\cdot)$ for arbitrary symmetric matrices $\mathbf{A}$ with algebraic complex values. Building on work by Dyer and Greenhill [Random Structures and Algorithms, 17 (2000), pp. 260--289], Bulatov and Grohe [Theoretical Computer Science, 348 (2005), pp. 148--186], and especially the recent beautiful work by Goldberg et al. [SIAM J. Comput., 39 (2010), pp. 3336--3402], we prove a complete dichotomy theorem for this problem. We show that $Z_{\mathbf{A}} (\cdot)$ is either computable in polynomial-time or \#P-hard, depending explicitly on the matrix $\mathbf{A}$. We further prove that the tractability criterion on $\mathbf{A}$ is polynomial-time decidable.

For certain subclasses of NP, $\oplus$P, or #P characterized by local constraints, it is known that if there exist any problems within that subclass that are not polynomial time computable, then all the problems in the subclass are NP-complete, $\oplus$P-complete, or #P-complete. Such dichotomy results have been proved for characterizations such as constraint satisfaction problems and directed and undirected graph homomorphism problems, often with additional restrictions. Here we give a dichotomy result for the more expressive framework of Holant problems. For example, these additionally allow for the expression of matching problems, which have had pivotal roles in the development of complexity theory. As our main result we prove the dichotomy theorem that, for the class $\oplus$P, every set of symmetric Holant signatures of any arities that is not polynomial time computable is $\oplus$P-complete. The result exploits some special properties of the class $\oplus$P and characterizes four distinct tractable subclasses within $\oplus$P. It leaves open the corresponding questions for NP, $\#$P, and $\#_k$P for $k\neq 2$.

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.

Holant is a framework of counting characterized by local constraints. It is closely related to other well-studied frameworks such as #CSP and Graph Homomorphism. An effective dichotomy for such frameworks can immediately settle the complexity of all combinatorial problems expressible in that framework. Both #CSP and Graph Homomorphism can be viewed as sub-families of Holant with the additional assumption that the equality constraints are always available. Other sub-families of Holant such as Holant* and Holantcproblems, in which we assume some specific sets of constraints to be freely available, were also studied. The Holant framework becomes more expressive and contains more interesting tractable cases with less or no freely available constraint functions, while, on the other hand, it also becomes more challenging to obtain a complete characterization of its time complexity. Recently, complexity dichotomy for a variety of sub-families of Holant such as #CSP, Graph Homomorphism, Holant* and Holantcwere proved. The dichotomy for the general Holant framework, which is the most desirable, still remains open. In this paper, we prove a dichotomy for the general Holant framework where all the constraints are real symmetric functions. This setting already captures most of the interesting combinatorial problems defined by local constraints, such as (perfect) matching, independent set, vertex cover and so on. This is the first time a dichotomy is obtained for general Holant Problems without any auxiliary functions. One benefit of working with Holant framework is some powerful new reduction techniques such as Holographic reduction. Along the proof of our dichotomy, we introduce a new reduction technique, namely realizing a constraint function by approximating it. This new technique is employed in our proof in a situation where it seems that all previous reduction techniques fail, thus this new idea of reduction might also be of independent interest. Besides proving dichotomy and developing new technique, we also obtained some interesting by-products. We prove a dichotomy for #CSP restricting to instances where each variable appears a multiple of d times for any d. We also prove that counting the number of Eulerian-Orientations on 2k-regular graphs is #P-hard for any k≥2.

We give the first deterministic fully polynomial-time approximation scheme (FPTAS) for computing the partition function of a two-state spin system on an arbitrary graph, when the parameters of the system satisfy the uniqueness condition on infinite regular trees. This condition is of physical significance and is believed to be the right boundary between approximable and inapproximable. The FPTAS is based on the correlation decay technique introduced by Bandyopadhyay and Gamarnik [1] and Weitz [61]. The classic correlation decay is defined with respect to graph distance. Although this definition has natural physical meanings, it does not directly support an FPTAS for systems on arbitrary graphs, because for graphs with unbounded degrees, the local computation that provides a desirable precision by correlation decay may take super-polynomial time. We introduce a notion of computationally efficient correlation decay, in which the correlation decay is measured in a refined metric instead of graph distance. We use a potential method to analyze the amortized behavior of this correlation decay and establish a correlation decay that guarantees an inverse-polynomial precision by polynomial-time local computation. This gives us an FPTAS for spin systems on arbitrary graphs. This new notion of correlation decay properly reflects the algorithmic aspect of the spin systems, and may be used for designing FPTAS for other counting problems.

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(log2n) 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."

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 it 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 tractability 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.

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.

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.

We prove a complexity dichotomy theorem for counting weighted Boolean CSP modulo k for any positive integer $k>1$. This generalizes a theorem by Faben for the unweighted setting. In the weighted setting, there are new interesting tractable problems. We first prove a dichotomy theorem for the finite field case where k is a prime. It turns out that the dichotomy theorem for the finite field is very similar to the one for the complex weighted Boolean #CSP, found by [Cai, Lu and Xia, STOC 2009]. Then we further extend the result to an arbitrary integer k.

We propose and explore a novel alternative framework to study the complexity of counting problems, called Holant problems. Compared to counting constraint satisfaction problems (#CSP), it is a refinement with a more explicit role for the constraint functions. Both graph homomorphism and #CSP can be viewed as special cases of Holant problems. We prove complexity dichotomy theorems in this framework. Our dichotomy theorems apply to local constraint functions, which are symmetric functions on Boolean input variables and evaluate to arbitrary real or complex values. We discover surprising tractable subclasses of counting problems, which could not easily be specified in the #CSP framework. When all unary functions are assumed to be free ($\mathrm{Holant}^*$ problems), the tractable ones consist of functions that are degenerate, or of arity at most two, or holographic transformations of Fibonacci gates. When only two special unary functions, the constant zero and constant one functions, are assumed to be free ($\mathrm{Holant}^c$ problems), we further identify three special families of tractable cases. Then we prove that all other cases are #P-hard. The main technical tool we use and develop is holographic reductions. Another technical tool used in combination with holographic reductions is polynomial interpolations.

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.

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 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}.

Valiant has proposed a new theory of algorithmic computation based on perfect matchings and Pfaffians. We study the properties of matchgates—the basic building blocks in this new theory. We give a set of algebraic identities which completely characterizes these objects for arbitrary numbers of inputs and outputs. These identities are derived from Grassmann-Plücker identities. The 4 by 4 matchgate character matrices are of particular interest. These were used in Valiant's classical simulation of a fragment of quantum computations. For these 4 by 4 matchgates, we use Jacobi's theorem on compound matrices to prove that the invertible matchgate matrices form a multiplicative group. Our results can also be expressed in the theory of Holographic Algorithms in terms of realizable standard signatures. These results are useful in establishing limitations on the ultimate capabilities of Valiant's theory of matchgate computations and Holographic Algorithms.

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.

We study the scheduling problem on unrelated machines in the mechanism design setting. This problem was proposed and studied in the seminal paper (Nisan and Ronen 1999), where they gave a 1.75-approximation randomized truthful mechanism for the case of two machines. We improve this result by a 1.6737-approximation randomized truthful mechanism. We also generalize our result to a $0.8368m$-approximation mechanism for task scheduling with $m$ machines, which improve the previous best upper bound of $0.875m(Mu'alem and Schapira 2007).

Holographic algorithms are a novel approach to design polynomial time computations using linear superpositions. Most holographic algorithms are designed with basis vectors of dimension 2. Recently Valiant showed that a basis of dimension 4 can be used to solve in P an interesting (restrictive SAT) counting problem mod 7. This problem without modulo 7 is #P-complete, and counting mod 2 is NP-hard. We give a general collapse theorem for bases of dimension 4 to dimension 2 in the holographic algorithms framework. We also define an extension of holographic algorithms to allow more general support vectors. Finally we give a Basis Folding Theorem showing that in a natural setting the support vectors can be simulated by bases of dimension 2.

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.