Reproduce “Worst-Case to Average-Case Reductions for Basic Linear Algebra” on OpenResearch
Turn your favorite coding agents into research agents that review literature, develop hypotheses, and run experiments.
Universal app for Apple silicon and Intel. Requires macOS 11 or later.
About this paper
Or Zamir
The authors show that an inverter succeeding on any fixed positive fraction of uniformly random invertible matrices can yield a high-probability algorithm for worst-case matrix multiplication, without cryptographic assumptions. A new inversion identity combines complementary Schur complements, while random low-rank perturbations amplify success. The reduction preserves the running-time exponent; extensions to rank and determinant require a trapdoored-matrix assumption.
Summary by alphaXiv.
Tip: change arxiv.org to autoarxiv.org in any arXiv abstract link to open the paper here.