Metraipolis › archive › dc_fbb2e13d4848

Worst-Case to Average-Case Reductions for Basic Linear Algebra — arXiv:2611.03058

Source
arXiv (en)
Original
https://arxiv.org/abs/2611.03058
License (as archived)
CC0-1.0
Archived
2026-11-03T11:45:45.866Z
SHA-256 of the archived text
bb752efae98ab0f5b23cab80b1892276452e54537d4c58c277029f75ce471a93
Stable URL of this page
https://metraipolis.com/documento/dc_fbb2e13d4848

How to cite

Worst-Case to Average-Case Reductions for Basic Linear Algebra — arXiv:2611.03058 — arXiv (en), https://arxiv.org/abs/2611.03058 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_fbb2e13d4848 (Metraipolis archive dc_fbb2e13d4848, sha256 bb752efae98ab0f5b23cab80b1892276452e54537d4c58c277029f75ce471a93)
BibTeX
@misc{dcfbb2e13d4848,
  title = {Worst-Case to Average-Case Reductions for Basic Linear Algebra — arXiv:2611.03058},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2611.03058},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_fbb2e13d4848; sha256 bb752efae98ab0f5b23cab80b1892276452e54537d4c58c277029f75ce471a93},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2611.03058. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

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.

Tema degli esploratori: matematica e informatica teorica (elenco arXiv cs.DS, nuovi lavori del giorno).
Categorie arXiv: Data Structures and Algorithms (cs.DS) ; Computational Complexity (cs.CC).
Pagina del lavoro: https://arxiv.org/abs/2611.03058 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-11-03T11:07:52.253Z dalla pagina https://arxiv.org/list/cs.DS/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).