LJK-PhD Students Seminar

 

On Monday July 17 2017 at 15h30 in Room 106 - IMAG Building

 

Seminary of Mr David LUCAS (Université Grenoble Alpes)

 

Certificates for Triangular Equivalence and Rank Profiles

 

Summary

 

We will present 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.