Worst-Case to Average-Case Reductions for Basic Linear Algebra
Or Zamir
cs.DS, cs.CC
2026-11-02
The first unconditional worst-case to average-case reduction for matrix inversion: an algorithm inverting any constant fraction of random matrices yields a worst-case one.
Matrix multiplication got a clean answer in 1993: Blum, Luby and Rubinfeld proved that an algorithm multiplying more than 75% of matrix pairs correctly can be converted into one handling every pair in essentially the same running time, and follow-up work pushed 75% down to any positive constant. The sibling operations lagged behind. Inversion, solving linear systems, computing rank and determinant are all computationally equivalent to matrix multiplication in the worst case, yet none had a comparable worst-case to average-case reduction. The obstruction is concrete: classical worst-case reductions query highly structured intermediate matrices, and an algorithm reliable only on uniform random inputs has no guarantee on those. Vaikuntanathan and Zamir recently filled the gap with trapdoor matrices, at the price of resting on cryptographic assumptions such as LPN. This paper attacks both open ends: whether the assumptions can be dropped, and how little success on random inputs suffices.
The unconditional reduction for inversion works in two layers.
The first layer handles success probability close to one and rests on a new identity. Sample a uniform R, invert R and I−R, embed the target product BC into two 2n×2n block matrices, make six inversion calls in total, and reassemble BC = BRC + B(I−R)C from two complementary Schur complements. The design point: as long as A, A′ and R are uniform, each of the six queried matrices is itself uniform once you condition on invertibility, which is exactly the regime an average-case inverter covers. The resulting average-case multiplication algorithm then takes the original BLR route, random shifts plus Freivalds checks, and becomes worst-case.
The second layer amplifies any constant success rate ε into that regime. Repeatedly apply rank-one perturbations A → A + uvᵀ. The Sherman–Morrison/Woodbury identity converts between the inverses before and after each perturbation at low cost, and Fourier analysis shows this random walk has a spectral gap: after O(log(1/ε)) steps the perturbed matrix is indistinguishable from uniform under any bounded test. The overhead is near-linear in 1/ε, and the paper proves this dependence is optimal.
The conditional part assumes trapdoor matrices, pseudorandom matrices whose vector action runs in near-linear time given a secret key. One observation carries a lot of weight: every such family automatically supports near-quadratic determinant computation and single-system solving, via Wiedemann's method with Berlekamp–Massey, so determinant thresholds that previously needed a stronger specialized assumption now follow from the generic one. The remaining reductions use rank profiles. Comparing the algorithm's output distribution on random matrices of prescribed rank against the masked target matrix, any ε advantage over a constant predictor must surface as a detectable difference at some rank level, exposing whether the target is invertible.
| Average-case success | Worst-case consequence | Assumption |
| Inversion, any constant ε | Matrix multiplication, hence inversion | Unconditional |
| Invertibility, max{s,1−s} + ε | Invertibility decision, exact rank | Trapdoor |
| Determinant, s + ε | Rank and invertibility | Trapdoor |
| On invertible inputs, 1/(q−1) + ε | Determinant modulo a subgroup of order < min{q−1, 2/ε} | Trapdoor |
| Over F₂₀₄₈, 0.044 + ε | Exact determinant | Trapdoor |
Here s is the probability that a uniform random matrix is singular, at most 1/(q−1). The invertibility and rank thresholds are optimal, asking only for a slight edge over the trivial algorithm that always returns the most likely answer. The inversion theorem itself: an algorithm running in time T(m) with success rate at least ε on uniform invertible matrices multiplies any n×n pair in Õε(T(2n)) with high probability. Dimension doubles, the exponent stays put. The exact determinant threshold drops to s + (1−s)/ℓ + ε, with ℓ the smallest prime factor of q−1; every previously known sufficient threshold exceeded 1/2. Taking q = 2^r for odd primes r gives infinitely many fields with threshold O(1/log q), as small as you want.
For practitioners this is conceptual calibration: under what conditions does average performance on random inputs convert into worst-case guarantees? Linear algebra is the substrate of large-scale computing and machine learning, and for inversion the answer is now unconditional, with a conversion bar as low as any constant success rate. To be clear about scope, this is pure complexity theory and nothing you compile tomorrow changes. The value is that open questions are being closed one at a time: inversion unconditionally, rank and invertibility at optimal thresholds, determinant stuck at a subgroup ambiguity. The acknowledgments also disclose extensive use of public AI tools as a speed multiplier for testing directions and filling technical gaps, with the core ideas and final versions attributed to the author.
The author lists three in the discussion section. Determinant reductions cannot cross the subgroup ambiguity of multiplicative masking: an algorithm that computes det(A) correctly but returns it multiplied by a random sign succeeds with probability above 1/2, and current techniques cannot separate det(A) from −det(A); this is tied to the open question of whether an invertibility oracle yields the determinant. The rank, invertibility and determinant reductions all rest on the existence of trapdoored matrices (LPN, McEliece-type assumptions), and removing them stays open, as does an unconditional reduction for solving a single linear system Ax = b. One detail that is easy to misread: the arbitrarily-small-threshold corollary fixes the field in advance and assumes the corresponding trapdoor family over that field. The most solid part of the paper is the unconditional inversion reduction, with a complete proof chain; the conditional results are worth exactly as much as your confidence in the trapdoor assumption.