Matrix Rigidity from the Viewpoint of Parameterized Complexity

DOI10.4230/LIPICS.STACS.2017.32MaRDI QIDQ4636630zbMATH OpenOpenAlexFDO

Authors Fedor V. Fomin, Daniel Lokshtanov, Saket Saurabh, Meirav Zehavi, S. M. Meesum

Publication date 19 April 2018

Full work available at URL https://doi.org/10.4230/LIPIcs.STACS.2017.32

zbMATH Keywords

parameterized complexitymatrix rigidity

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Combinatorial aspects of matrices (incidence, Hadamard, etc.) (05B20) Computational aspects of higher-dimensional varieties (14Q15)

Recommendations

• Matrix Rigidity from the Viewpoint of Parameterized Complexity
• On the Complexity of Matrix Rank and Rigidity
• On the complexity of matrix rank and rigidity
• A note on matrix rigidity
• Theory and Applications of Models of Computation
• A remark on matrix rigidity
• Matrix and tensor rigidity and L_p-approximation
• Rigidity theory for matroids
• Efficient Construction of Rigid Matrices Using an NP Oracle
• Rigidity Matroids

Cited in

(14)

• Reliability analysis in interdependent smart grid systems
• Lower Bounds on Matrix Rigidity Via a Quantum Argument
• Cascading critical nodes detection with load redistribution in complex systems
• Matrix rigidity and the Croot-Lev-Pach lemma
• Will electrical cyber-physical interdependent networks undergo first-order transition under random attacks?
• On the complexity of matrix rank and rigidity
• Catastrophic cascading failures in power networks
• Some combinatorial-algebraic problems from complexity theory
• On the Complexity of Matrix Rank and Rigidity
• Spectral methods for matrix rigidity with applications to size-depth trade-offs and communication complexity
• Algorithms for NP-Hard Problems via Rank-Related Parameters of Matrices
• Matrix Rigidity from the Viewpoint of Parameterized Complexity
• Sociotechnical network analysis for power grid resilience in South Korea
• Parameterized low-rank binary matrix approximation

This page was built for publication: Matrix Rigidity from the Viewpoint of Parameterized Complexity

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