Matrix Rigidity from the Viewpoint of Parameterized Complexity
From MaRDI portal
Publication:4638994
DOI10.1137/17M112258XzbMath1394.68177OpenAlexW2802074115WikidataQ129898753 ScholiaQ129898753MaRDI QIDQ4638994
Meirav Zehavi, Fedor V. Fomin, Daniel Lokshtanov, Saket Saurabh, Syed M. Meesum
Publication date: 2 May 2018
Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/17m112258x
Analysis of algorithms and problem complexity (68Q25) Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Vector spaces, linear dependence, rank, lineability (15A03)
Related Items (2)
Parameterized analysis and crossing minimization problems ⋮ Parameterized low-rank binary matrix approximation
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- A remark on matrix rigidity
- Fundamentals of parameterized complexity
- Using elimination theory to construct rigid matrices
- A note on matrix rigidity
- Application of separability and independence notions for proving lower bounds of circuit complexity
- On the computational complexity and geometry of the first-order theory of the reals. I: Introduction. Preliminaries. The geometry of semi-algebraic sets. The decision problem for the existential theory of the reals
- On the rigidity of Vandermonde matrices
- On space and depth in resolution
- Rank Reduction of Directed Graphs by Vertex and Edge Deletions
- Hadamard’s Determinant Inequality
- Reducing Rank of the Adjacency Matrix by Graph Modification
- Complexity Lower Bounds using Linear Algebra
- On the Complexity of Matrix Rank and Rigidity
- Sampling-based dimension reduction for subspace approximation
- Fixed-parameter Approximability of Boolean MinCSPs
- Parameterized Algorithms
- Automata, Languages and Programming
- Editing the Simplest Graphs
This page was built for publication: Matrix Rigidity from the Viewpoint of Parameterized Complexity
