The computational complexity of some problems of linear algebra
From MaRDI portal
Publication:1307698
DOI10.1006/jcss.1998.1608zbMath0941.68059OpenAlexW1969557621WikidataQ105972786 ScholiaQ105972786MaRDI QIDQ1307698
Jonathan F. Buss, Gudmund Skovbjerg Frandsen, Jeffrey O. Shallit
Publication date: 8 February 2000
Published in: Journal of Computer and System Sciences (Search for Journal in Brave)
Full work available at URL: https://semanticscholar.org/paper/12eb4101b800d31bee35d1399bea7e767c8b6d02
Related Items (42)
Efficient key recovery for all HFE signature variants ⋮ A Combinatorial Algorithm for Computing the Rank of a Generic Partitioned Matrix with 2 $$\times $$ 2 Submatrices ⋮ Constructive non-commutative rank computation is in deterministic polynomial time ⋮ An inexact proximal DC algorithm with sieving strategy for rank constrained least squares semidefinite programming ⋮ Checking strict positivity of Kraus maps is NP-hard ⋮ Cryptanalysis of HFE, multi-HFE and variants for odd and even characteristic ⋮ Practical post-quantum signature schemes from isomorphism problems of trilinear forms ⋮ General linear group action on tensors: a candidate for post-quantum cryptography ⋮ Non-commutative Edmonds' problem and matrix semi-invariants ⋮ On the complexity of the generalized MinRank problem ⋮ A family of weak keys in HFE and the corresponding practical key-recovery ⋮ Revisiting algebraic attacks on MinRank and on the rank decoding problem ⋮ Connections between graphs and matrix spaces ⋮ Refined F5 Algorithms for Ideals of Minors of Square Matrices ⋮ Improving support-minors rank attacks: applications to G\textit{e}MSS and Rainbow ⋮ LRPC codes with multiple syndromes: near ideal-size KEMs without ideals ⋮ Improvement of algebraic attacks for solving superdetermined MinRank instances ⋮ MinRank in the head. Short signatures from zero-knowledge proofs ⋮ MR-DSS -- smaller MinRank-based (ring-)signatures ⋮ Algebraic relation of three MinRank algebraic modelings ⋮ RAC-Drawability is ∃ℝ-complete and Related Results ⋮ Improvements of algebraic attacks for solving the rank decoding and MinRank problems ⋮ Unnamed Item ⋮ Zero forcing in iterated line digraphs ⋮ Fixed points, Nash equilibria, and the existential theory of the reals ⋮ The real computational complexity of minmax value and equilibrium refinements in multi-player games ⋮ The product of matrix subspaces ⋮ On the complexity of matrix rank and rigidity ⋮ The complexity of tensor rank ⋮ A proximal DC approach for quadratic assignment problem ⋮ Unnamed Item ⋮ Minimal rank completions for overlapping blocks ⋮ Square, a New Multivariate Encryption Scheme ⋮ On the computational complexity of decision problems about multi-player Nash equilibria ⋮ An algebraic attack on rank metric code-based cryptosystems ⋮ Roots of Square: Cryptanalysis of Double-Layer Square and Square+ ⋮ From Independent Sets and Vertex Colorings to Isotropic Spaces and Isotropic Decompositions: Another Bridge between Graphs and Alternating Matrix Spaces ⋮ Rank minimization with applications to image noise removal ⋮ A combinatorial algorithm for computing the rank of a generic partitioned matrix with \(2 \times 2\) submatrices ⋮ On the Complexity of Some Geometric Problems With Fixed Parameters ⋮ Generalized Wong sequences and their applications to Edmonds' problems ⋮ An algebraic approach to the rank support learning problem
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- A note on matrix rigidity
- 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
- Optimization, approximation, and complexity classes
- A quantifier elimination for the theory of \(p\)-adic numbers
- Maximum rank matrix completion
- Hilbert's Nullstellensatz is in the polynomial hierarchy
- A determinantal version of the frobenius-könig theorem
- Fast Probabilistic Algorithms for Verification of Polynomial Identities
- Fast parallel matrix and GCD computations
- Decision procedures for real and p‐adic fields
- Systems of distinct representatives and linear algebra
- \(p\)-adic numbers. An introduction
This page was built for publication: The computational complexity of some problems of linear algebra
