Research map / Learning theory and algorithms / Sample complexity
On the (In)tractability of Computing Normalizing Constants for the Product of Determinantal Point Processes
Naoto Ohsaka, Tatsuya Matsuoka
Read the paperCheck your idea against 137,217 papers
AI-extracted. The measured effects below were read by AI from the paper's full text (no summary yet). Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Restrict exponentiated DPP matrix to (-1,0,1)-matrix or P-matrix, with exponent p fixed positive even integer | Exponentiated DPP normalizing constant Z_p(A) · Complexity (exact computation mod 3) | computational hardness (UP-hard and Mod3P-hard) | Hurt |
| Use three positive semi-definite matrices instead of two in the product DPP | Product DPP normalizing constant Z_m · Approximation complexity | approximability (factor 2^{O(|I|^{1-eps})} NP-hard) | Hurt |
| Parameterize by maximum rank of two PSD matrices (FPT algorithm) | Z2(A,B) computation · Exact computation, running time r^{O(r)} n^{O(1)} | computational tractability (FPT) | Improved |
| Parameterize by treewidth of union of nonzero patterns (FPT algorithm) | Z2(A,B) computation · Exact computation, running time w^{O(w)} n^{O(1)} | computational tractability (FPT) | Improved |
| Parameterize by maximum treewidth of A and B separately | Z2(A,B) computation · Exact computation with treewidth at most 3 | computational tractability (#P-hard) | Hurt |
Closest papers by meaning
- Learning Determinantal Point Processes with Moments and Cycles (ICML 2017 · similarity 0.88)
- Exact sampling of determinantal point processes with sublinear time preprocessing (NeurIPS 2019 · similarity 0.87)
- Kronecker Determinantal Point Processes (NeurIPS 2016 · similarity 0.87)
- Learning Signed Determinantal Point Processes through the Principal Minor Assignment Problem (NeurIPS 2018 · similarity 0.86)
- A Polynomial Time MCMC Method for Sampling from Continuous Determinantal Point Processes (ICML 2019 · similarity 0.86)
- Small coresets via negative dependence: DPPs, linear statistics, and concentration (NeurIPS 2024 · similarity 0.82)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.
