On the complexity of approximating extremal determinants in matrices
From MaRDI portal
Publication:1346597
DOI10.1006/JCOM.1995.1005zbMATH Open0819.65085OpenAlexW2005482089MaRDI QIDQ1346597FDOQ1346597
Authors: Leonid G. Khachiyan 
Publication date: 5 April 1995
Published in: Journal of Complexity (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1006/jcom.1995.1005
Recommendations
- On largest volume simplices and sub-determinants
- The computational complexity of some problems of linear algebra
- The (Non)enumerability of the determinant and the rank
- Approximating the complexity measure of Vavasis-Ye algorithm is NP-hard
- On selecting a maximum volume sub-matrix of a matrix and related problems
Complexity and performance of numerical algorithms (65Y20) Numerical computation of determinants (65F40)
Cited In (25)
- Optimal resilient sensor placement problem for secure state estimation
- Phase retrieval from very few measurements
- Uniform excess frames in Hilbert spaces
- Cardinality minimization, constraints, and regularization: a survey
- On the parameterized complexity of \textsc{Girth} and \textsc{Connectivity} problems on linear matroids
- LWE with side information: attacks and concrete security estimation
- Undirected determinant and its complexity
- On the hardness of approximating the permanent of structured matrices
- An easily computable upper bound on the Hoffman constant for homogeneous inequality systems
- Sum-of-squares optimization without semidefinite programming
- Computing the Degree of Determinants via Discrete Convex Optimization on Euclidean Buildings
- \(O(n\log^ 2n)\) determinant computation of a Toeplitz matrix and fast variance estimation
- A primal-dual interior point method whose running time depends only on the constraint matrix
- Deterministic APSP, Orthogonal Vectors, and More
- Title not available (Why is that?)
- Subdeterminant maximization via nonconvex relaxations and anti-concentration
- On the fraction of matrices with maximal additive complexity
- On the tractability of some natural packing, covering and partitioning problems
- On extremal behaviors of Murty's least index method
- On the computational complexity of the secure state-reconstruction problem
- Sampling-based dimension reduction for subspace approximation with outliers
- The complexity of finding the minimal of the maximum cycle means of similar zero-one matrices
- Scientific contributions of Leo Khachiyan (a short overview)
- Supersaturated designs with the maximum number of factors for a given resolution-rank
- Exponential inapproximability of selecting a maximum volume sub-matrix
This page was built for publication: On the complexity of approximating extremal determinants in matrices
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1346597)
