Certificates for triangular equivalence and rank profiles - CASYS Access content directly
Conference Papers Year : 2017

Certificates for triangular equivalence and rank profiles

Abstract

In this paper, we give novel certificates for triangular equivalence and rank profiles. These certificates enable to verify the row or column rank profiles or the whole rank profile matrix faster than recomputing them, with a negligible overall overhead. We first provide quadratic time and space non-interactive certificates saving the logarithmic factors of previously known ones. Then we propose interactive certificates for the same problems whose Monte Carlo verification complexity requires a small constant number of matrix-vector multiplications, a linear space, and a linear number of extra field operations. As an application we also give an interactive protocol, certifying the determinant of dense matrices, faster than the best previously known one.
Fichier principal
Vignette du fichier
rpm_certificate.pdf (240.85 Ko) Télécharger le fichier
Origin : Files produced by the author(s)
Loading...

Dates and versions

hal-01466093 , version 1 (13-02-2017)
hal-01466093 , version 2 (20-10-2019)

Identifiers

Cite

Jean-Guillaume Dumas, David Lucas, Clément Pernet. Certificates for triangular equivalence and rank profiles. ACM International Symposium on Symbolic and Algebraic Computations - ISSAC'17, Jul 2017, Kaiserslautern, Germany. pp.133-140, ⟨10.1145/3087604.3087609⟩. ⟨hal-01466093v2⟩
526 View
232 Download

Altmetric

Share

Gmail Facebook X LinkedIn More