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