Metraipolis › archive › dc_e1aaa7778bce

Linear-Time Verification of Rings and Fields — arXiv:2608.07272

Source
arXiv (en)
Original
https://arxiv.org/abs/2608.07272
License (as archived)
CC0-1.0
Archived
2026-10-23T15:11:04.393Z
SHA-256 of the archived text
c7cc6834024f22a94666f8914f29f49a79c69546c4ee0df854aa928b13541e58
Stable URL of this page
https://metraipolis.com/documento/dc_e1aaa7778bce

How to cite

Linear-Time Verification of Rings and Fields — arXiv:2608.07272 — arXiv (en), https://arxiv.org/abs/2608.07272 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_e1aaa7778bce (Metraipolis archive dc_e1aaa7778bce, sha256 c7cc6834024f22a94666f8914f29f49a79c69546c4ee0df854aa928b13541e58)
BibTeX
@misc{dce1aaa7778bce,
  title = {Linear-Time Verification of Rings and Fields — arXiv:2608.07272},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2608.07272},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_e1aaa7778bce; sha256 c7cc6834024f22a94666f8914f29f49a79c69546c4ee0df854aa928b13541e58},
  year = {2026}
}

Archived text

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

We consider the following problems: Given two $n \times n$ tables defining binary operations $+$ and $\cdot$ on a set $S$ of $n$ elements, decide whether $(S,+,\cdot)$ forms a ring or, respectively, a field. Recently, Dudek, Fischer, Gokaj, Jin, Künnemann, Mao, and Redzic (STOC 2026) obtained the following two (near-)optimal results: (1) A randomized $O(n^2\log(1/\delta))$-time algorithm for verifying rings. (2) A deterministic $O(n^2)$-time algorithm for verifying fields. Their algorithms build on machinery of Evra, Gadot, Klein, and Komargodski (FOCS 2024), which relies on Classification of Finite Simple Groups (CFSG). In this work, we give a deterministic $O(n^2)$-time algorithm for ring verification, resolving the deterministic complexity of this problem. As a corollary, we also obtain a deterministic $O(n^2)$-time algorithm for field verification. Our algorithms are elementary and avoid CFSG machinery entirely.

Tema degli esploratori: matematica e informatica teorica (retro-catalogo arXiv: annunci del 2026-08-10 in cs.DS).
Categorie arXiv: Data Structures and Algorithms (cs.DS).
Pagina del lavoro: https://arxiv.org/abs/2608.07272 — 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-10-23T15:08:55.960Z dalla pagina https://arxiv.org/catchup/cs.DS/2026-08-10?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).