Certificates and probabilistic verification


Séminaire Modèles et Algorithmes Déterministes: CASYS

14/06/2012 - 09:45 Mr Dave Saunders Salle 2 - Tour IRMA

I will discuss verification techniques that can be of use in both the theory and the practice of exact linear algebra.

The complexity theory of linear algebra is in a state paralleling the P, NP dicotomy to some extent.  Let L be the class of problems that can be solved in time essentially linear in the input size (essentially means that logarithmic factors are allowed).  Matrix multiplication may be in L or not (for n by n matrices, linear time would be a cost of essentially n2).  But the current best known exponent of matrix multiplication is 2.37.  If multiplication is in L, so are a number of other linear algebra problems that can be reduced
to multiplication (some of which are known to be equivalent).  It is not known whether matrix multiplication is even in NL (nondeterministic linear time).  But we do have it in PNL (probabilistic nondeterministic linear time). That is to say we have a certificate that can be probabilistically checked in linear time.  I will discuss this and probabilistic certificates for other linear algebra problems.

In practice, for sparse and structured matrices, we have available a suite of probabilistic blackbox algorithms for linear algebra.  Many of them are proven effective only for large fields.  But we know from experience that the proven probability bounds are either not sharp or sharp only for rarely occurring worst cases.  Also many of the analyses are unduly pessimistic about the range of field sizes over which they work.  I will explain how probabilistic methods can be applied outside their range of proven effectiveness if supplemented with a probabilistic verification.  This brings a number of methods from the realm of heuristic into the realm of Monte Carlo algorithm.
It can be of great practical benefit, removing significant logarithmic and constant factors from run times.