Deterministic polynomial time algorithms for matrix completion problems

DOI10.1137/090781231MaRDI QIDQ5390613zbMATH OpenOpenAlexFDO

Authors Gábor Ivanyos, Nitin Saxena, 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

zbMATH Keywords

generatorsidentity testingmatrix completionmodulesmorphisms

Mathematics Subject Classification ID

Modules, bimodules and ideals in associative algebras (16D99) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Symbolic computation and algebraic computation (68W30)

Recommendations

• Fast deterministic algorithms for matrix completion problems
• Fast deterministic algorithms for matrix completion problems
• Deterministic network coding by matrix completion
• Maximum rank matrix completion
• The computational complexity of some problems of linear algebra

Cited in

(31)

• Maximum rank matrix completion
• On the complexity of the permanent in various computational models
• Linear matroid intersection is in quasi-NC
• General linear group action on tensors: a candidate for post-quantum cryptography
• Computing the interleaving distance is NP-hard
• On the normal forms of modules with respect to parametrizing bimodules.
• Generalized Wong sequences and their applications to Edmonds' problems
• 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
• The complexity of binary matrix completion under diameter constraints
• Jacobian hits circuits: hitting sets, lower bounds for depth-D occur-k formulas and depth-3 transcendence degree-k circuits
• Deterministic network coding by matrix completion
• On the Expressive Power of Read-Once Determinants
• Linear Time Interactive Certificates for the Minimal Polynomial and the Determinant of a Sparse Matrix
• Subspace arrangements, graph rigidity and derandomization through submodular optimization
• A deterministic PTAS for the commutative rank of matrix spaces
• Algorithms based on \(*\)-algebras, and their applications to isomorphism of polynomials with one secret, group isomorphism, and polynomial identity testing
• Fast deterministic algorithms for matrix completion problems
• Fast deterministic algorithms for matrix completion problems
• Computing the Degree of Determinants via Discrete Convex Optimization on Euclidean Buildings
• Algorithms for group isomorphism via group extensions and cohomology
• Improved Algorithms for Alternating Matrix Space Isometry: From Theory to Practice
• On the Complexity of Isomorphism Problems for Tensors, Groups, and Polynomials I: Tensor Isomorphism-Completeness
• Connections between graphs and matrix spaces
• Group factorisation for smaller signatures from cryptographic group actions
• Pauli flow on open graphs with unknown measurement labels
• Hitting sets for orbits of circuit classes and polynomial families
• On p-group isomorphism: search-to-decision, counting-to-decision and nilpotency class reductions via tensors
• Structural preprocessing method for nonlinear differential-algebraic equations using linear symbolic matrices
• Spanning trees of 3-uniform hypergraphs
• On the complexity of isomorphism problems for tensors, groups, and polynomials. I: Tensor isomorphism-completeness

This page was built for publication: Deterministic polynomial time algorithms for matrix completion problems

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