This work gives a deterministic $O(n^2)$-time algorithm for ring verification and obtains a deterministic $O(n^2)$-time algorithm for field verification, resolving the deterministic complexity of this problem.
Abstract
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\"unnemann, 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.
We exhibit two explicit circulant graphs of prime order $251$ that are $K_4$-free and have independence number $19$. Consequently \[R(4,20)\ge 252.\] These improve the bound $R(4,20)\ge 237$ given by Nagda, Raghavan, Thakurta and the long standing bound $R(4,21)\ge 242$ recorded in Radziszowski's dynamic survey. The gr...
For integers $d\geq 3$, let $F_{2,d}(n)$ be the largest size of a subset of $[n]$ containing no two distinct elements whose product is a perfect $d$-th power, and let $f_{2,d}(n)$ denote the analogous quantity when the two elements need not be distinct. Fleiner, Juh\'asz, K\"ov\'er, Pach, and S\'andor proved that both...
For a fixed integer $t\geq 3$, consider families of $t$-mark Golomb rulers whose positive-difference sets are pairwise disjoint and contained in $[1,U]$. Let $P_t(U)$ be the largest number of integers covered by such a family. We determine the threshold for asymptotically complete coverage: \[ P_t(U)=U-o(U) \quad\Longl...
The finite group isomorphism problem asks whether two finite groups of order $N$ are isomorphic. The first algorithm, attributed to Tarjan (see Miller, STOC'78), runs in time $N^{\log N + O(1)}$. Despite intensive study, the current best known algorithm has a running time of $N^{(1 / 4 + o(1))\log N}$ (Rosenbaum,'13)....
Joshua A. Grochow, Gábor Ivanyos, You-Ming Qiao et al.· 0 citations
For every odd integer $t\ge17$, we prove that an explicit circulant graph on $5t-10$ vertices is doubly saturated $R(3,t)$-good. The graph is triangle-free and has independence number $t-1$. Adding any nonedge creates a triangle, whereas deleting any edge creates an independent set of order $t$. This settles Conjecture...
Abhishek Saigal, Akaash R. Parthasarathy· 0 citations
We give a deterministic algorithm that computes the parity of the number of Hamiltonian cycles in an $n$-vertex directed graph in $O(n^4(3/2)^n)$ time and $O(n^2)$ bits of working space, improving the $O^*(\varphi^n)$ bound of Bj\"orklund and Husfeldt. Their local-degree formula reduces the problem to a weighted sum ov...
Han-Qing Li· 0 citations
We use cookies to run the site and, with your consent, for analytics and to show ads.
See our Cookie Policy.
