Mathematical Foundations of Computer Science 2005

DOI10.1007/11549345MaRDI QIDQ5492879zbMATH OpenOpenAlexFDO

Authors Leonid Gurvits

Publication date 20 October 2006

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/11549345

Mathematics Subject Classification ID

Determinants, permanents, traces, other special matrix functions (15A15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25) Randomized algorithms (68W20) Approximation algorithms (68W25)

Recommendations

• Stability and complexity of mixed discriminants
• Computing mixed discriminants, mixed volumes, and permanents
• A deterministic polynomial-time algorithm for approximating mixed discriminant and mixed volume
• A deterministic algorithm for approximating the mixed discriminant and mixed volume, and a combinatorial corollary
• On The Complexity of Computing Mixed Volumes

Cited in

(21)

• Computing mixed discriminants, mixed volumes, and permanents
• A deterministic algorithm for approximating the mixed discriminant and mixed volume, and a combinatorial corollary
• A stability result using the matrix norm to bound the permanent
• Spanning tree constrained determinantal point processes are hard to (approximately) evaluate
• A quantum hash function with grouped coarse-grained boson sampling
• Computing the permanent of (some) complex matrices
• A deterministic polynomial-time algorithm for approximating mixed discriminant and mixed volume
• scientific article; zbMATH DE number 3952960 (Why is no real title available?)
• On the analytic complexity of discriminants
• Approximating permanents and hafnians
• On the classical complexity of sampling from quantum interference of indistinguishable bosons
• On the complexity of constrained determinantal point processes
• A Tight Analysis of Bethe Approximation for Permanent
• Some Inapproximability Results of MAP Inference and Exponentiated Determinantal Point Processes
• scientific article; zbMATH DE number 7250159 (Why is no real title available?)
• Stability and complexity of mixed discriminants
• Log-concave polynomials. II: High-dimensional walks and an FPRAS for counting bases of a matroid
• A tight analysis of Bethe approximation for permanent
• New inequalities for permanents and hafnians and some generalizations
• Parameterized applications of symbolic differentiation of (totally) multilinear polynomials
• An efficient tree decomposition method for permanents and mixed discriminants

This page was built for publication: Mathematical Foundations of Computer Science 2005

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5492879)