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.
More from Research
- w2v-bert-fast open-sources exact 3x speedup for w2v-BERT 2.0 training and inference — kastnerkyle · 2026-11-23
- AI reads 2,000 historical illustrations: individual errors, near-perfect aggregate patterns — _akpiper · 2026-11-23
- Princeton/Meta evolve inference strategies: 39% cheaper Qwen3 runs, same accuracy — michaelTM_ai · 2026-11-23
- MIT approach enables physically consistent AI models of chaotic systems — SnoozeDoggyDog · 2026-11-23
- ReLU networks have zero second derivative almost everywhere — why PINNs need smooth activations — bravo_abad · 2026-11-22
- Sinclair lab uses AI to find chemical age-reversal molecules, mouse tissues rejuvenated in 4 weeks — thederbiedone · 2026-11-22