On the Complexity of Constrained Determinantal Point Processes

DOI10.4230/LIPIcs.APPROX-RANDOM.2017.36zbMath1467.68062arXiv1608.00554OpenAlexW2963923611MaRDI QIDQ5002639

Damian Straszak, Nisheeth K. Vishnoi, Tarun Kathuria, Amit Deshpande, L. Elisa Celis

Publication date: 28 July 2021

Full work available at URL: https://arxiv.org/abs/1608.00554

zbMATH Keywords

polynomialsmatroidsconstraintsdeterminantal point processesmixed discriminantsampling and counting

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Point processes (e.g., Poisson, Cox, Hawkes processes) (60G55) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87)

Related Items (4)

Ranking with Fairness Constraints ⋮ Stability and complexity of mixed discriminants ⋮ Subdeterminant Maximization via Nonconvex Relaxations and Anti-Concentration ⋮ Spanning tree constrained determinantal point processes are hard to (approximately) evaluate

Cites Work

• Unnamed Item
• Unnamed Item
• Mixed discriminants of positive semidefinite matrices
• Random generation of combinatorial structures from a uniform distribution
• Computing mixed discriminants, mixed volumes, and permanents
• A deterministic algorithm for approximating the mixed discriminant and mixed volume, and a combinatorial corollary
• Interlacing families. II: Mixed characteristic polynomials and the Kadison-Singer problem
• A polynomial-time approximation algorithm for the permanent of a matrix with nonnegative entries
• Graphical Models, Exponential Families, and Variational Inference
• Information, Physics, and Computation
• Cooling Schedules for Optimal Annealing
• A random polynomial-time algorithm for approximating the volume of convex bodies
• Counting Minimum Weight Spanning Trees
• Real stable polynomials and matroids: optimization and counting
• Pipage Rounding, Pessimistic Estimators and Matrix Concentration
• Mathematical Foundations of Computer Science 2005
• Solving convex programs by random walks

This page was built for publication: On the Complexity of Constrained Determinantal Point Processes