The computational complexity of some problems of linear algebra
From MaRDI portal
Recommendations
Cites work
- \(p\)-adic numbers. An introduction
- 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 parallel matrix and GCD computations
- Fast Probabilistic Algorithms for Verification of Polynomial Identities
- Hilbert's Nullstellensatz is in the polynomial hierarchy
- 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?)
- 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
Cited in
(71)- The complexity of linear problems in fields
- The communication complexity of several problems in matrix computation
- On the complexity of approximating extremal determinants in matrices
- Linear complexity algorithm for semiseparable matrices
- Constructive non-commutative rank computation is in deterministic polynomial time
- Zero forcing in iterated line digraphs
- The complexity of matrix rank and feasible systems of linear equations
- A proximal DC approach for quadratic assignment problem
- Minimal rank completions for overlapping blocks
- An algebraic attack on rank metric code-based cryptosystems
- A combinatorial algorithm for computing the rank of a generic partitioned matrix with 2 2 submatrices
- An algebraic approach to the rank support learning problem
- Efficient key recovery for all HFE signature variants
- An inexact proximal DC algorithm with sieving strategy for rank constrained least squares semidefinite programming
- Practical post-quantum signature schemes from isomorphism problems of trilinear forms
- General linear group action on tensors: a candidate for post-quantum cryptography
- The product of matrix subspaces
- On the complexity of matrix rank and rigidity
- Generalized Wong sequences and their applications to Edmonds' problems
- Non-commutative Edmonds' problem and matrix semi-invariants
- Detecting matrices of combinatorial rank three
- Improvements of algebraic attacks for solving the rank decoding and MinRank problems
- Roots of Square: cryptanalysis of double-layer Square and Square+
- Combinatorial optimization methods to determine the rank of a matrix over a commutative ring, with engineering applications
- A family of weak keys in HFE and the corresponding practical key-recovery
- Checking strict positivity of Kraus maps is NP-hard
- Cryptanalysis of HFE, multi-HFE and variants for odd and even characteristic
- Computational Complexity and Numerical Stability of Linear Problems
- Square, a New Multivariate Encryption Scheme
- Complexity of Solving Linear Systems in Different Models of Computation
- On the complexity of the generalized MinRank problem
- scientific article; zbMATH DE number 1256731 (Why is no real title available?)
- scientific article; zbMATH DE number 2072707 (Why is no real title available?)
- Interval Linear Algebra and Computational Complexity
- A deterministic PTAS for the commutative rank of matrix spaces
- From independent sets and vertex colorings to isotropic spaces and isotropic decompositions: another bridge between graphs and alternating matrix spaces
- A combinatorial algorithm for computing the rank of a generic partitioned matrix with \(2 \times 2\) submatrices
- Algorithms for NP-Hard Problems via Rank-Related Parameters of Matrices
- The complexity of MinRank
- The computational complexity of some problems of linear algebra (extended abstract)
- Fixed points, Nash equilibria, and the existential theory of the reals
- Deterministic polynomial time algorithms for matrix completion problems
- On the complexity of some geometric problems with fixed parameters
- On the computational complexity of decision problems about multi-player Nash equilibria
- The real computational complexity of minmax value and equilibrium refinements in multi-player games
- 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
- scientific article; zbMATH DE number 7692356 (Why is no real title available?)
- 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
- Computational complexity of decision problems about Nash equilibria in win-lose multi-player games
- A polynomial time key-recovery attack on the Sidon cryptosystem
- VDOO: a short, fast, post-quantum multivariate digital signature scheme
- Some computational problems in linear algebra as hard as matrix multiplication
- Pauli flow on open graphs with unknown measurement labels
- Smaller public keys for MinRank-based schemes
- On the arithmetic complexity of computing Gröbner bases of comaximal determinantal ideals
- State of the art of HFE variants. Is it possible to repair HFE with appropriate modifiers?
- The complexity of tensor rank
- On the complexity of the relative eigenvector problem
- Public-key encryption from the MinRank problem
- Hybrid subsupport guessing: a new hybrid technique for the rank decoding problem
- Fault attacks on MPCitH signature schemes
- On the complexity, tractability and group theoretic applications of the relative eigenvector problem
- Rank minimization with applications to image noise removal
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)
