# Some Inapproximability Results of MAP Inference and Exponentiated Determinantal Point Processes

arXiv: https://arxiv.org/abs/2109.00727 · HTML: https://mlsanity.com/paper/2109.00727/

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 12 of its 59 references that are in the map.
- First posted on arXiv 2 Sep 2021.

## Builds on (most cited first, 12 of 12)

- [Batch Active Learning Using Determinantal Point Processes](https://mlsanity.com/paper/1906.07975/) (2019)
- [Faster Greedy MAP Inference for Determinantal Point Processes](https://mlsanity.com/paper/1703.03389/) (2017)
- [Scalable Learning and MAP Inference for Nonsymmetric Determinantal Point Processes](https://mlsanity.com/paper/2006.09862/) (2020)
- [Randomized Rounding for the Largest Simplex Problem](https://mlsanity.com/paper/1412.0036/) (2014)
- [Deterministic Algorithms for Submodular Maximization Problems](https://mlsanity.com/paper/1508.02157/) (2015)
- [Large-Margin Determinantal Point Processes](https://mlsanity.com/paper/1411.1537/) (2014)
- [Log-Concave Polynomials II: High-Dimensional Walks and an FPRAS for Counting Bases of a Matroid](https://mlsanity.com/paper/1811.01816/) (2018)
- [On largest volume simplices and sub-determinants](https://mlsanity.com/paper/1406.3512/) (2014)
- [Flexible Modeling of Diversity with Strongly Log-Concave Distributions](https://mlsanity.com/paper/1906.05413/) (2019)
- [Block-Wise MAP Inference for Determinantal Point Processes with Application to Change-Point Detection](https://mlsanity.com/paper/1503.06239/) (2015)
- [A Generalization of Permanent Inequalities and Applications in Counting and Optimization](https://mlsanity.com/paper/1702.02937/) (2017)
- [Maximizing Determinants under Matroid Constraints](https://mlsanity.com/paper/2004.07886/) (2020)

## Built on by (most cited first, 3 of 3)

- [Lazy and Fast Greedy MAP Inference for Determinantal Point Process](https://mlsanity.com/paper/2206.05947/) (2022)
- [Computational Complexity of Normalizing Constants for the Product of Determinantal Point Processes](https://mlsanity.com/paper/2111.14148/) (2021)
- [Spectral Certificates and Projection-DPP Rounding for Determinantal MAP Selection](https://mlsanity.com/paper/2606.19411/) (2026)

## Abstract (arXiv)

We study the computational complexity of two hard problems on determinantal point processes (DPPs). One is maximum a posteriori (MAP) inference, i.e., to find a principal submatrix having the maximum determinant. The other is probabilistic inference on exponentiated DPPs (E-DPPs), which can sharpen or weaken the diversity preference of DPPs with an exponent parameter p. We present several complexity-theoretic hardness results that explain the difficulty in approximating MAP inference and the normalizing constant for E-DPPs. We first prove that unconstrained MAP inference for an n × n matrix is textsfNP-hard to approximate within a factor of 2β n, where β = 10^-1013 . This result improves upon the best-known inapproximability factor of (frac98-ε), and rules out the existence of any polynomial-factor approximation algorithm assuming textsfP neq textsfNP. We then show that log-determinant maximization is textsfNP-hard to approximate within a factor of frac54 for the unconstrained case and within a factor of 1+10^-1013 for the size-constrained monotone case. In particular, log-determinant maximization does not admit a polynomial-time approximation scheme unless textsfP = textsfNP. As a corollary of the first result, we demonstrate that the normalizing constant for E-DPPs of any (fixed) constant exponent p ≥ β-1 = 10^1013 is textsfNP-hard to approximate within a factor of 2β pn, which is in contrast to the case of p ≤ 1 admitting a fully polynomial-time randomized approximation scheme.