Fall 2014

Essentially Optimal Interactive Certificates in Linear Algebra

Thursday, September 18th, 2014 2:00 pm2:50 pm

Add to Calendar


Calvin Lab Auditorium

Certificates to a linear algebra computation are additional data structures for each output, which can be used by a---possibly randomized---verification algorithm that proves the correctness of each output. The certificates are essentially optimal if the time (and space) complexity of verification is essentially linear in the input size N, meaning N times a factor N^{o(1)}, that is, a factor N^{\eta(N)} with \lim_{N\to \infty} \eta(N) = 0.

We give algorithms that compute essentially optimal certificates for the positive semidefiniteness, Frobenius form, characteristic and minimal polynomial of an n\times n dense integer matrix A. Our certificates can be verified in Monte-Carlo bit complexity (n^2 \log ||A||)^{1+o(1)}, where \log ||A|| is the bit size of the integer entries, solving an open problem in [Kaltofen, Nehring, Saunders, Proc. ISSAC 2011] subject to computational hardness assumptions.

Second, we give algorithms that compute certificates for the rank of sparse or structured n\times n matrices over an abstract field, whose Monte Carlo verification complexity is 2 matrix-times-vector products + n^{1+o(1)} arithmetic operations in the field. For example, if the n\times n input matrix is sparse with n^{1+o(1)} non-zero entries, our rank certificate can be verified in n^{1+o(1)} field operations. This extends also to integer matrices with only an extra \log||A||^{1+o(1)} factor.

All our certificates are based on interactive verification protocols with the interaction removed by a Fiat-Shamir identification heuristic. The validity of our verification procedure is subject to standard computational hardness assumptions from cryptography. Our certificates improve on those by Goldwasser, Kalai and Rothblum 2008 and Thaler 2012 for our problems in the prover complexity, and are independent of the circuits that compute them thus detecting programming errors in them.

This is joint work with Jean-Guillaume Dumas at the University of Grenoble.