Matrix inversion worst-case efficiency achieved from average-case algorithms
Worst-Case to Average-Case Reductions for Basic Linear Algebra
Data Structures and AlgorithmsComputational Complexity
Summary
Some math problems on matrices are tricky to solve in the worst case, but often easier on average. This paper shows it is possible to turn an algorithm that works well on a decent number of average-case inputs for matrix inversion into one that works well on all inputs. The authors also improve similar results for deciding if a matrix is invertible, calculating its rank, and finding its determinant. These findings hold without relying on any extra assumptions for matrix inversion and with weaker assumptions for related problems.
What this means in practice
- •For cryptographic engineers: Design cryptographic schemes relying on secure matrix inversion algorithms validated under worst-case assumptions.
- •For algorithm designers: Build efficient matrix computation tools knowing that average-case success rates guarantee worst-case performance.
A theory result. No direct application yet.
Authors
Or Zamir
Abstract
We study worst-case to average-case reductions for basic linear-algebraic problems over finite fields. A seminal work of Blum, Luby, and Rubinfeld established that any algorithm that successfully multiplies more than $75\%$ of matrix pairs over any finite field, implies an algorithm with essentially the same running time multiplying any pair of matrices. A sequence of follow-ups reduced the needed fraction of successful input pairs to any positive constant. Despite most of the other basic linear algebraic operations being computationally equivalent to matrix multiplication in the worst case, no such worst-case to average-case reductions were known for them. Recently, Vaikuntanathan and Zamir introduced a cryptographic primitive called trapdoor matrices and used them to prove such worst-case to average-case reductions for matrix inversion, solving a linear system, and computing the determinant, all conditioned on common cryptographic assumptions. Our main result is the first unconditional time-preserving worst-case to average-case reduction for matrix inversion. Any algorithm that correctly inverts any constant positive fraction of uniformly random invertible matrices implies a worst-case such algorithm. We also significantly strengthen the conditional reductions based on trapdoored matrices: We establish reductions for deciding invertibility and computing rank at the optimal success thresholds, and qualitatively improve the success threshold needed in the reduction for determinant computation---while previous reductions all required the success probability to be at least $1/2$, we show that any fixed positive average-case success probability suffices for exact worst-case determinant computation over infinitely many finite fields.