AI Paper Atlas

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

ICML 2020 · Learning theory and algorithms › Sample complexity · approach: Private and query-efficient algorithms · 3 citations (OpenAlex)

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 changedWhereMeasuredEffect
Restrict exponentiated DPP matrix to (-1,0,1)-matrix or P-matrix, with exponent p fixed positive even integerExponentiated 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 DPPProduct DPP normalizing constant Z_m · Approximation complexityapproximability (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 separatelyZ2(A,B) computation · Exact computation with treewidth at most 3computational tractability (#P-hard)Hurt

Closest papers by meaning

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.

Open scime draft

Get the next scime Dispatch and a monthly field update

Free. We send a confirmation link first; every email has a one-click unsubscribe. Privacy