CS Paper Radar

On computing the determinant over a ring

Gilles Villard

cs.SC cs.CC ·submitted 2026-11-05 10:26 UTC · v1

Abstract

An algorithm is presented for computing the determinant and the characteristic polynomial of a matrix $A$ over an arbitrary commutative ring R. The algorithm uses $O(n^ω)$ ring additions, subtractions and multiplications, where $ω>2$ is a feasible exponent for matrix multiplication, that is, such that two $n\times n$ matrices over R can be multiplied using $O(n^ω)$ ring operations. The algorithm involves no division and no zero test, and its control depends only on $n$: for each $n$ it is a straight-line program. The approach combines a polynomial matrix point of view and a block Krylov point of view on the characteristic polynomial, which makes Strassen's elimination of divisions efficient. A bivariate matrix $λI-L(t)$, obtained from $A$ by a homotopy, is compressed in $\log n$ steps, each of which halves the dimension while only doubling the degree in $λ$. The cost of the homotopy is controlled by truncating the power series in $t$ at an order that only grows with the compression steps, from a constant to $n$.

Closest papers

Nearest neighbours by meaning across the whole index.

Computing the Determinant via the Generalized Euclidean Algorithm

cs.DS cs.SC ·2026-08-22 ·Janina Reuter
similarity 0.64
Abstract

We present an algorithm with a natural geometric interpretation for computing the determinant of a matrix $B\in\mathbb{Z}^{d\times d}$. It improves upon the current fastest deterministic algorithms by a factor of $d^{ω(1)+1-ω(2)}\approx d^{0.1213}$, where $ω(k)$ denotes the exponent required for multiplying a $d\times d$ matrix with a $d\times d^k$ matrix. Our approach builds on a recent result of Klein and Reuter (STOC 2025), who introduced a novel algorithmic idea for lattice basis computation that can be viewed as extending the Euclidean algorithm from $\mathbb{Z}$ to $\mathbb{Z}^d$. By adapting their techniques, we compute the determinant with the same bit complexity as applying the generalized Euclidean algorithm to an input matrix $A\in\mathbb{Z}^{d\times 2d}$ with $\|A\| = \|B\|$, namely $\tilde{O}(d^{ω(2)}\log\|B\|)$. Prior to this work, the fastest deterministic algorithm for computing the determinant required $\tilde{O}(d^{ω(1)+1}\log\|B\|)$ bit operations.

0.22

Explicit matrix hitting points for noncommutative algebraic branching programs

cs.CC math.RAmath.CO ·2026-10-11 ·Zhipeng Lu
similarity 0.63
Abstract · 24 pages. There's statement about reproducibility and Lean verification in section 5

We give a deterministic polynomial-resource black-box identity test for noncommutative algebraic branching programs (ABPs), using ordinary matrix evaluations of the output polynomial. Given an alphabet of size $m\ge1$ and an ABP vertex bound $S\ge1$, we construct one fixed tuple of integer matrices of order $R=(m+2)d(d+1)/2$, where $d=(m+2)S$, with entry bit length $O(d\log(d+1))$. Every nonzero polynomial computed by an ABP with at most $S$ vertices has a nonzero evaluation at this tuple. The construction accesses neither the hidden ABP nor its intermediate gates. A rectangular variant improves the order to $O(m^{3/2}S^2)$. Matrix order, description length, and all returned entries are counted; the total resources are polynomial. The result holds in characteristic zero and in characteristic $p>\binom d2$. The main ingredient is a fixed polynomial frame spanning the joint cyclic module of every matrix tuple from every prescribed vector. A compensating block makes a tagged encoding nilpotent of index at most three, while preserving the original cyclic module. A differential exterior-vector argument then gives a single triangular recurrence with polynomially many outputs. Its shared left-linear circuit is converted into actual integer query matrices by coefficient duality. Two-sided pairing further gives deterministic nonadaptive reconstruction of an equivalent ABP from polynomially many output-only matrix queries. The same frame gives polynomial-cardinality explicit trace separators for simultaneous-conjugation orbit closures, and a fixed nilpotent substitution for bounded-dimensional recognizable series. The latter also tests rational formulas whose given syntax is defined at the scalar origin. We provide complete proofs, construction costs, and exact implementation checks.

0.16

Worst-Case to Average-Case Reductions for Basic Linear Algebra

cs.DS cs.CC ·2026-11-02 ·Or Zamir
similarity 0.61
Abstract

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.

0.30

Matrix Multiplication from Polynomial Packings: A Constructive and Elementary Proof of $ω\le9/4$

cs.CC ·2026-10-20 ·Rafael Pass
similarity 0.60
Abstract

We give a self-contained constructive proof that the matrix multiplication exponent satisfies $ω\le9/4$. In a recent breakthrough, OpenAI~\cite{original} established this bound in the model of exact scalar arithmetic over the complex numbers, using non-constructive arguments in Strassen's asymptotic spectral framework. We explicitly construct a Strassen-style matrix multiplication identity and obtain the bound by ordinary block recursion. For every $γ>0$, the resulting algorithm multiplies two $n\times n$ integer matrices using $O(n^{9/4+γ})$ integer arithmetic operations. As an independent contribution, we develop a framework of \emph{polynomial packings}---methods for reducing many polynomial multiplications to fewer ones using linear operations. We isolate and generalize a construction of OpenAI~\cite{original} to obtain a simple packing, and show how packings can be composed to amplify their ``compression rate", which finally yields Strassen-like identities.

0.07

Efficient Algorithms for Subdeterminant Maximization under Partition Matroids

cs.DS cs.DM ·2026-09-16 ·Nikhil Bansal, Yuze Xu
publishedhot direction similarity 0.57
Abstract · Under submission to SODA 2027. The authors used GPT-5.5 Pro during the development of this work to explore proof strategies, search for rela…

We consider the determinant maximization problem under partition constraints: Given an $n\times n$ PSD matrix A and a partition matroid $M$ on $[n]$, find a base $S$ of $M$ that maximizes $\det(A_{S,S})$. We give an $e^{O(k)}$-approximation algorithm to find such a set $S$, where $k$ is the rank of $M$. This improves upon the current $k^{O(k)}$-approximation, and matches the current $e^k$-estimation guarantee, up to $O(1)$ factors in the exponent. Our algorithm is based on rounding the geometric max-min relaxation due to Nikolov-Singh'2016, using a continuous potential-driven process, and several new structural and analytic properties of this relaxation.

0.31

Improved Degree Tables for Secure Distributed Matrix Multiplication

cs.IT math.CO ·2026-09-06 ·John Byrne, Rafael G. L. D'Oliveira, Michael Tait
theory similarity 0.57
Abstract

In secure distributed matrix multiplication, a user wishes to compute the product of two matrices with the assistance of servers, in such a way that any $T$ colluding servers learn nothing about either matrix. Degree tables are a combinatorial tool for constructing polynomial codes for this problem and underlie several state-of-the-art schemes, including $\mathsf{GASP}_r$, $\mathsf{GASP}_{r,s}$, and $\mathsf{DOG}_{r,s}$. We introduce a periodic-gap framework for constructing degree tables that contains these three families as special cases and leads to two new constructions, $\mathsf{SHIFT}_{r,s}$ and $\mathsf{COVER}_r$. We determine their exact recovery thresholds and show that, in many cases, they outperform the current state of the art. We also prove a new lower bound on the recovery threshold of ordinary integer degree tables. In the balanced case, in which the partitioning parameters and the security parameter are equal, we sharpen this bound to match $\mathsf{SHIFT}_{r,s}$ up to lower-order terms, showing that it is asymptotically optimal among degree-table constructions.

0.14

Eigensolvers for polynomial roots and tensor decomposition

cs.MS cs.SCmath.ACmath.AG ·2026-08-20 ·Enrica Barrilli, Bernard Mourrain
similarity 0.57
Abstract

Computing eigenvalues and eigenvectors is at the heart of the solution of many non-linear problems. For instance, finding the roots of polynomial systems reduces to computing joint eigenvectors of operators of multiplication. Similarly, tensor decomposition can be performed via the joint diagonalization of submatrices of the Catalecticant of the tensor. We describe and illustrate symbolic-numeric methods for computing the solutions of these algebraic problems from the computation of joint eigenvectors of commuting operators, and for analysing their multiplicity structure, as well as their implementation in the package AlgebraicSolvers.jl.

0.31

Simple, Faster (min, +) Matrix Multiplication and APSP

cs.DS ·2026-10-14 ·Barna Saha, Christopher Ye
theory similarity 0.57
Abstract · 17 pages

In this note, we provide a deterministic algorithm that computes the $(\min, +)$-Matrix Product $C = A * B$ of two $N \times N$ matrices $A$ and $B$ with polynomially bounded integer entries in $\tilde{O}(N^{2.9964})$ time, improving upon the exponent of $O(N^{2.9995})$ time obtained in the recent breakthrough by Anthropic (Alman and Vassilevska Williams, 2026). Our algorithm uses a phased approach first proposed by Bringmann, Grandoni, Saha, and Vassilevska Williams in 2016. The phased approach produces an approximation $\tilde{C}$ of $C$ in truly subcubic time such that the number of remaining triples $(i,k,j): A_{i,k}+B_{k,j} < \tilde{C}(i,j)$ is truly subcubic. This provided strong evidence that a truly subcubic $(\min, +)$-Matrix Product and therefore, a truly subcubic algorithm for All Pairs Shortest Paths (APSP) may exist. However, to find the remaining triples in subcubic time, a sparse certificate is needed whose construction was not known. We use the thin matrix product theorem of the recent breakthrough to provide such a certificate. This gives a simple modular subcubic algorithm for APSP.

0.46