Motivated by studying the power of randomness, certifying algorithms and barriers for fine-grained reductions, we investigate the question whether the multiplication of two @math matrices can be performed in near-optimal nondeterministic time @math . Since a classic algorithm due to Freivalds verifies correctness of matrix products probabilistically in time @math , our question is a relaxation of the open problem of derandomizing Freivalds' algorithm. We discuss consequences of a positive or negative resolution of this problem and provide potential avenues towards resolving it. Particularly, we show that sufficiently fast deterministic verifiers for 3SUM or univariate polynomial identity testing yield faster deterministic verifiers for matrix multiplication. Furthermore, we present the partial algorithmic progress that distinguishing whether an integer matrix product is correct or contains between 1 and @math erroneous entries can be performed in time @math -- interestingly, the difficult case of deterministic matrix product verification is not a problem of "finding a needle in the haystack", but rather cancellation effects in the presence of many errors. Our main technical contribution is a deterministic algorithm that corrects an integer matrix product containing at most @math errors in time @math . To obtain this result, we show how to compute an integer matrix product with at most @math nonzeroes in the same running time. This improves upon known deterministic output-sensitive integer matrix multiplication algorithms for @math nonzeroes, which is of independent interest.
Let A and B two n×n matrices over a ring R (e.g., the reals or the integers) each containing at most m nonzero elements. We present a new algorithm that multiplies A and B using O(m0.7n1.2+n2+o(1)) algebraic operations (i.e., multiplications, additions and subtractions) over R. The naive matrix multiplication algorithm, on the other hand, may need to perform o(mn) operations to accomplish the same task. For m≤n1.14, the new algorithm performs an almost optimal number of only n2+o(1) operations. For m≤n1.68, the new algorithm is also faster than the best known matrix multiplication algorithm for dense matrices which uses O(n2.38) algebraic operations. The new algorithm is obtained using a surprisingly straightforward combination of a simple combinatorial idea and existing fast rectangular matrix multiplication algorithms. We also obtain improved algorithms for the multiplication of more than two sparse matrices. As the known fast rectangular matrix multiplication algorithms are far from being practical, our result, at least for now, is only of theoretical value. We describe almost optimal (on the average) combinatorial algorithms for the following algorithmic problems : (i) computing the boolean matrix product, (ii) finding witnesses for boolean matrix multiplication and (iii) computing the diameter and all-pairs-shortest-paths of a given (unweighted) graph digraph. For each of these problems, we assume that the input instances are drawn from suitable distributions. A random boolean matrix (graph digraph) is one in which each entry (edge arc) is set to 1 or 0 (included) independently with probability p. Even though fast algorithms have been proposed earlier, they are based on algebraic approaches which are complex and difficult to implement. Our algorithms are purely combinatorial in nature and are much simpler and easier to implement. They are based on a simple combinatorial approach to multiply boolean matrices. Using this approach, we design fast algorithms for (a) computing product and witnesses when A and B both are random boolean matrices or when A is random and B is arbitrary but fixed (or vice versa) and (b) computing diameter, distances and shortest paths between all pairs in the given random graph digraph. Our algorithms run in O(n2(log n)) time with O(n-3) failure probability thereby yielding algorithms with expected running times within the same bounds. Our algorithms work for all values of p. We use randomness to exploit the potential sparsity of the Boolean matrix product in order to speed up the computation of the product. Our new fast output-sensitive algorithm for Boolean matrix product and its witnesses is randomized and provides the Boolean product and its witnesses almost certainly. Its worst-case time performance is expressed in terms of the input size and the number of non-zero entries of the product matrix. It runs in time @math , where the input matrices have size n×n, the number of non-zero entries in the product matrix is at most s, ? is the exponent of the fast matrix multiplication and @math denotes O(f(n)log? d n) for some constant d. By the currently best bound on ?, its running time can be also expressed as @math . Our algorithm is substantially faster than the output-sensitive column-row method for Boolean matrix product for s larger than n 1.232 and it is never slower than the fast @math -time algorithm for this problem. By applying the fast rectangular matrix multiplication, we can refine our upper bound further to the form @math , where ?(p,q,t) is the exponent of the fast multiplication of an n p ×n q matrix by an n q ×n t matrix. We also present a partial derandomization of our algorithm as well as its generalization to include the Boolean product of rectangular Boolean matrices. Finally, we show several applications of our output-sensitive algorithms. 