题目：      Essentially Optimal Interactive Certificates in Linear Algebra

报告人：     Erich Kaltofen  (North Carolina State University, USA)

时间地点：2014.08.07  3:00pm  N420

   摘要：        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 No(1), that is, a factor Nη(N) with limN→∞η(N)=0. 
                         We give algorithms that compute essentially optimal certificates for the positive semidefiniteness, Frobenius form, characteristic and

                         minimal polynomial of an n×n dense integer matrix A. Our certificates can be verified in Monte-Carlo bit complexity (n2log||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×n matrices over an abstract field, whose Monte

                         Carlo verification complexity is 2 matrix-times-vector products + n1+o(1) arithmetic operations in the field. For example, if the n×n input

                         matrix is sparse with n1+o(1) non-zero entries, our rank certificate can be verified in n1+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 circuit that computes them thus detecting programming errors in them. 
                         This is joint work with Jean-Guillaume Dumas at the University of Grenoble.