First unconditional reduction shows matrix inversion is as hard on random inputs as worst case

_onionesque · x · 2026-11-03

Building on the Blum-Luby-Rubinfeld result that matrix multiplication is as hard on random inputs as in the worst case, the author gives the first unconditional such reduction for matrix inversion, plus conditional reductions (via trapdoor matrices) for singularity, rank, and determinant. A theoretical CS / complexity theory advance.

Original post →

More from Research

Research channel →