Deterministic Polynomial Time Algorithms for Matrix Completion Problems
From MaRDI portal
Publication:5390613
DOI10.1137/090781231zbMath1209.68269OpenAlexW2058463226MaRDI QIDQ5390613
Nitin Saxena, Gábor Ivanyos, Marek Karpinski
Publication date: 4 April 2011
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/090781231
Symbolic computation and algebraic computation (68W30) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Modules, bimodules and ideals in associative algebras (16D99)
Related Items (19)
Algorithms for Group Isomorphism via Group Extensions and Cohomology ⋮ On the Complexity of Isomorphism Problems for Tensors, Groups, and Polynomials I: Tensor Isomorphism-Completeness ⋮ General linear group action on tensors: a candidate for post-quantum cryptography ⋮ Non-commutative Edmonds' problem and matrix semi-invariants ⋮ Tripartite-to-bipartite entanglement transformation by stochastic local operations and classical communication and the structure of matrix spaces ⋮ On the Expressive Power of Read-Once Determinants ⋮ Connections between graphs and matrix spaces ⋮ Computing the interleaving distance is NP-hard ⋮ Subspace Arrangements, Graph Rigidity and Derandomization Through Submodular Optimization ⋮ Algorithms Based on *-Algebras, and Their Applications to Isomorphism of Polynomials with One Secret, Group Isomorphism, and Polynomial Identity Testing ⋮ Improved Algorithms for Alternating Matrix Space Isometry: From Theory to Practice ⋮ On the normal forms of modules with respect to parametrizing bimodules. ⋮ On the complexity of the permanent in various computational models ⋮ Spanning trees of 3-uniform hypergraphs ⋮ Linear matroid intersection is in quasi-NC ⋮ Unnamed Item ⋮ Jacobian Hits Circuits: Hitting Sets, Lower Bounds for Depth-$D$ Occur-$k$ Formulas and Depth-3 Transcendence Degree-$k$ Circuits ⋮ Computing the Degree of Determinants via Discrete Convex Optimization on Euclidean Buildings ⋮ Generalized Wong sequences and their applications to Edmonds' problems
This page was built for publication: Deterministic Polynomial Time Algorithms for Matrix Completion Problems
