The computational complexity of some problems of linear algebra
From MaRDI portal
Recommendations
Cites work
- scientific article; zbMATH DE number 3876606 (Why is no real title available?)
- scientific article; zbMATH DE number 4107004 (Why is no real title available?)
- scientific article; zbMATH DE number 3698383 (Why is no real title available?)
- scientific article; zbMATH DE number 42574 (Why is no real title available?)
- scientific article; zbMATH DE number 41838 (Why is no real title available?)
- scientific article; zbMATH DE number 44676 (Why is no real title available?)
- scientific article; zbMATH DE number 3467028 (Why is no real title available?)
- scientific article; zbMATH DE number 3597878 (Why is no real title available?)
- scientific article; zbMATH DE number 1261801 (Why is no real title available?)
- scientific article; zbMATH DE number 510841 (Why is no real title available?)
- scientific article; zbMATH DE number 1559516 (Why is no real title available?)
- scientific article; zbMATH DE number 3422402 (Why is no real title available?)
- A determinantal version of the frobenius-könig theorem
- A note on matrix rigidity
- A quantifier elimination for the theory of \(p\)-adic numbers
- Decision procedures for real and p‐adic fields
- Fast Probabilistic Algorithms for Verification of Polynomial Identities
- Fast parallel matrix and GCD computations
- Hilbert's Nullstellensatz is in the polynomial hierarchy
- Maximum rank matrix completion
- 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
- Systems of distinct representatives and linear algebra
- \(p\)-adic numbers. An introduction
Cited in
(60)- VDOO: a short, fast, post-quantum multivariate digital signature scheme
- RAC-Drawability is ∃ℝ-complete and Related Results
- Computational complexity of decision problems about Nash equilibria in win-lose multi-player games
- MinRank in the head. Short signatures from zero-knowledge proofs
- A polynomial time key-recovery attack on the Sidon cryptosystem
- Algebraic relation of three MinRank algebraic modelings
- MR-DSS -- smaller MinRank-based (ring-)signatures
- The product of matrix subspaces
- Some computational problems in linear algebra as hard as matrix multiplication
- General linear group action on tensors: a candidate for post-quantum cryptography
- Non-commutative Edmonds' problem and matrix semi-invariants
- Minimal rank completions for overlapping blocks
- Checking strict positivity of Kraus maps is NP-hard
- Improving support-minors rank attacks: applications to G\textit{e}MSS and Rainbow
- Improvements of algebraic attacks for solving the rank decoding and MinRank problems
- Generalized Wong sequences and their applications to Edmonds' problems
- Square, a New Multivariate Encryption Scheme
- An algebraic approach to the rank support learning problem
- Efficient key recovery for all HFE signature variants
- From independent sets and vertex colorings to isotropic spaces and isotropic decompositions: another bridge between graphs and alternating matrix spaces
- Constructive non-commutative rank computation is in deterministic polynomial time
- Computational Complexity and Numerical Stability of Linear Problems
- A combinatorial algorithm for computing the rank of a generic partitioned matrix with \(2 \times 2\) submatrices
- Roots of Square: cryptanalysis of double-layer Square and Square+
- Rank minimization with applications to image noise removal
- The computational complexity of some problems of linear algebra (extended abstract)
- scientific article; zbMATH DE number 7692356 (Why is no real title available?)
- A proximal DC approach for quadratic assignment problem
- Algorithms for NP-Hard Problems via Rank-Related Parameters of Matrices
- A combinatorial algorithm for computing the rank of a generic partitioned matrix with \(2 \times 2\) submatrices
- A family of weak keys in HFE and the corresponding practical key-recovery
- Zero forcing in iterated line digraphs
- A deterministic PTAS for the commutative rank of matrix spaces
- On the complexity of matrix rank and rigidity
- Improvement of algebraic attacks for solving superdetermined MinRank instances
- scientific article; zbMATH DE number 2072707 (Why is no real title available?)
- Complexity of Solving Linear Systems in Different Models of Computation
- Cryptanalysis of HFE, multi-HFE and variants for odd and even characteristic
- On the complexity of the generalized MinRank problem
- Deterministic polynomial time algorithms for matrix completion problems
- On the computational complexity of decision problems about multi-player Nash equilibria
- LRPC codes with multiple syndromes: near ideal-size KEMs without ideals
- An algebraic attack on rank metric code-based cryptosystems
- On the complexity of some geometric problems with fixed parameters
- Detecting matrices of combinatorial rank three
- The complexity of linear problems in fields
- The complexity of tensor rank
- Refined F5 Algorithms for Ideals of Minors of Square Matrices
- Fixed points, Nash equilibria, and the existential theory of the reals
- Interval Linear Algebra and Computational Complexity
- On the complexity of approximating extremal determinants in matrices
- Revisiting algebraic attacks on MinRank and on the rank decoding problem
- The complexity of MinRank
- Linear complexity algorithm for semiseparable matrices
- The real computational complexity of minmax value and equilibrium refinements in multi-player games
- Combinatorial optimization methods to determine the rank of a matrix over a commutative ring, with engineering applications
- An inexact proximal DC algorithm with sieving strategy for rank constrained least squares semidefinite programming
- Connections between graphs and matrix spaces
- Practical post-quantum signature schemes from isomorphism problems of trilinear forms
- The complexity of matrix rank and feasible systems of linear equations
This page was built for publication: The computational complexity of some problems of linear algebra
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1307698)
