CS Paper Radar

Partial Homogenization and the Structure of Optimal Algebraic Algorithms

Yuval Spiizer

cs.SC ·submitted 2026-11-17 23:34 UTC · v1
theory

Abstract

A quadratic map, such as the product of two polynomials, two complex numbers or two matrices, is classically computed by products of two linear forms. By Strassen's homogenization, their least number is also the least number of product gates of fan-in two. With unbounded fan-in, terms of higher degree can cancel, so the classical lower bounds and classifications do not apply. We ask whether unbounded fan-in beats fan-in two, and what the optimal circuits are. Our tool is constant-free partial homogenization, which keeps the terms of higher degree. Let a quadratic map have $K$ independent outputs. We prove that, under a mild condition, unbounded fan-in needs as many product gates as fan-in two whenever fan-in two needs at most $K+2$. For $2\times2$ matrix multiplication, we classify all optimal circuits with fan-in two and arbitrary constants. We prove that none of them nests products, and that their quadratic parts are Strassen's algorithm, one new algorithm, the Waksman-type algorithms, or a one-parameter family. Over $\mathbb{R}$, we prove that unbounded fan-in needs at least $6$ product gates, and approximate circuits exactly $5$. Below the threshold $K+2$, we prove that optimal circuits are rigid, for every fan-in. Every optimal circuit for polynomial multiplication is Toom-Cook at unisolvent points, up to constant scalings and shifts. Every optimal circuit for a tubal ring over $\mathbb{C}$ applies its transform. Every optimal circuit for complex multiplication over $\mathbb{R}$ is Gauss's algorithm at three real points, after a rotation. In at least two variables, every optimal division-free homogeneous component extractor is Ben-Or's construction with shifted points. Above the threshold, for $c\ge2$ complex products over $\mathbb{R}$, we prove that fan-in two needs exactly $3c$ product gates, unbounded fan-in at least $2c+2$, and approximate circuits exactly $2c+1$.

Closest papers

Nearest neighbours by meaning across the whole index.

Depth Hierarchies for Symmetric Algebraic Circuits

cs.CC ·2026-11-17 ·Anuj Dawar, Prateek Dwivedi, Benedikt Pago, Tim Seppelt
similarity 0.61
Abstract · submitted to STOC 2027

Algebraic complexity studies the cost of computing families of polynomials by algebraic circuits, with the central goal of proving super-polynomial circuit lower bounds and separations between different models of algebraic computation. Since such lower bounds remain elusive for general circuits, a common strategy is to focus on restricted models. A recent line of work (ICALP 2020, ITCS & STOC 2026) introduces and studies symmetry as a syntactic circuit restriction, showing exponential symmetric lower bounds for the permanent, as well as separations between symmetric analogues of algebraic formulas ($\mathsf{VF}$), skew circuits ($\mathsf{VS}$), and circuits ($\mathsf{VP}$). We investigate the role of depth as a complexity parameter in symmetric circuits. For every fixed $Δ\geq 1$, we exhibit a family of polynomials computable by symmetric circuits of polynomial size and depth $2Δ+3$, but requiring size $n^{Ω(\log n)}$ at depth $Δ$. We also define symmetric versions of the bounded-depth algebraic complexity classes $\mathsf{VAC}^k$, for all $k \in \mathbb{N}$, that we call $\mathsf{symVAC}^k$, and establish two strict hierarchies: Firstly, a hierarchy within $\mathsf{symVAC}^0$, and secondly, a hierarchy of the form $\mathsf{symVAC}^k \subsetneq \mathsf{symVAC}^{k+1}$ for all $k$. The latter shows that symmetric circuits of depth $(\log n)^{k+1}$ are strictly more powerful than depth-$(\log n)^k$ circuits. Moreover, we place the bounded-depth classes within the landscape of symmetric algebraic complexity developed by Dwivedi, Pago and Seppelt (STOC 2026). We complement this picture by introducing $\mathsf{symVNP}$, a symmetric analogue of $\mathsf{VNP}$, and establishing $\mathsf{symVNP}$-completeness of the permanent under symmetric projections.

0.33

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

cs.CC ·2026-10-20 ·Rafael Pass
similarity 0.59
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

A Dichotomy for Exact Quantum Circuit Amplitudes

cs.CC ·2026-11-17 ·Chenghua Liu, Boning Meng
similarity 0.59
Abstract

We classify the complexity of exactly computing computational-basis amplitudes for circuits over any fixed finite library of unitary qubit gates, with each gate allowed to act on any ordered tuple of distinct wires. Exact evaluation is polynomial-time computable if all gates permute the computational basis up to phases, all preserve product states, or all become Clifford under a common diagonal one-qubit unitary change of basis on every wire. For every other library, the problem is $\#\mathrm P$-hard under polynomial-time Turing reductions. Our proof connects circuit amplitudes to the Boolean Holant classification of tensor contractions on arbitrary graphs. For an algebraic library containing a nonmonomial gate and an entangling gate, we show how to simulate the joint use of a symmetric maximally entangled state and its adjoint at polynomial cost, using only amplitude queries over the original library. This lets us evaluate unrestricted contractions of the resulting gate and boundary tensors. Unitarity and the computational-basis boundaries then restrict the tractable cases to the three forms above. Algebraic specialization extends the dichotomy to arbitrary fixed complex gate entries under a symbolic exact-output convention.

0.33

Generalized Fibonacci gates are Frobenius algebras: a proof of Liu's conjecture

cs.CC ·2026-10-13 ·Aaron Sterling
unusual similarity 0.59
Abstract

Liu introduced generalized Fibonacci gates on domains of size 3 and 4, proved that Holant problems built from them are tractable by a cut-and-merge algorithm, and conjectured that Fibonacci gates with matching polynomial-time algorithms exist on all higher domains. We extend the definition uniformly to every domain size $k$ and show that a family of domain-$k$ generalized Fibonacci gates is the same thing as a $k$-dimensional commutative Frobenius (equivalently, Artinian Gorenstein) algebra $A$ equipped with an orthonormal basis containing $1$. Under this dictionary Liu's parameter constraints are exactly associativity of $A$, a gate is an element $w\in A$, merging two gates is multiplication in $A$, and the Holant value of a connected graph $G$ is $τ\bigl(h^{\,|E|-|V|+1}\prod_v w_v\bigr)$ for a fixed ``handle'' element $h\in A$. This proves Liu's conjecture for every $k$, with an algorithm whose cost is polynomial in $k$ as well as in the graph. We also give a closure criterion for linear recurrences of any depth (a balance condition implies closure, and is necessary when the unit is a combination of the colours), and we map the landscape: semisimple algebras are exactly Liu's orthogonal frames, smoothable algebras with nilpotents are collided frames, and families whose algebra is not smoothable (``frameless'' families) exist exactly when $k\ge 14$. Finally we show that every non-semisimple part of a family is invisible to the Holant on connected graphs with two or more independent cycles. This note states the results and sketches the proofs; the proofs of the main theorems are short and are given essentially in full.

0.27

Unrestricted Boolean Multiplicative Complexity of Four-Term Binary Polynomial Multiplication: Rational Places, Hasse Jets, and the Failure of Nonlinear Feedback

cs.CC cs.DS ·2026-08-31 ·Gregory Morse
theorycode/data similarity 0.59
Abstract · 25 pages, 1 table. Complete Lean 4 formalization and verification artifacts: https://github.com/GregoryMorse/unrestricted-boolean-mul

Classical lower bounds show that multiplying two degree-three polynomials over $\mathbb F_2$ requires nine scalar products in bilinear or quadratic models. They do not settle unrestricted Boolean multiplicative complexity: an XOR--AND circuit may reuse nonlinear intermediate wires, and Boolean equality is taken modulo $x_i^2=x_i$, so a multiplication can lower algebraic degree. Let $\operatorname{Mul}_4:\mathbb F_2^8\to\mathbb F_2^7$ output the seven coefficients of the product of two four-term binary polynomials. We prove that its unrestricted XOR--AND multiplicative complexity is exactly nine. This resolves, for a natural vector-valued quadratic function, the Boyar--Find question of whether a quadratic-circuit lower bound can persist against unrestricted nonlinear reuse. The proof is structural rather than exhaustive. A useful purely quadratic prefix is forced onto the three rational places of $\mathbb P^1(\mathbb F_2)$. In a hypothetical eight-AND circuit, the unique non-useful gate must carry a cubic high part. Any useful continuation then forces a rational tangent and exposes a first Hasse jet, while exterior jet separation together with Boolean idempotence prevents the same defect from exposing the second Hasse jet. The required useful suffix therefore cannot exist. A complete Lean 4 formalization verifies the Boolean-ANF semantics, the unrestricted circuit model, and the exact theorem; it uses no project-specific axiom or native decision procedure. The same zero-defect flag argument gives multiplicative complexity six for three-term multiplication, and the method isolates the multi-defect obstruction for five terms.

0.43

An Operator Approach to Register Programs for Catalytic Computing

cs.CC ·2026-09-16 ·Antoine Vinciguerra
theory similarity 0.58
Abstract

In a seminal work, Buhrman et al.\ (STOC 2014) introduced catalytic computation and proved that uniform $TC^1$ circuits are computable in catalytic logspace, the class of problems solvable in space $s$ with an additional catalytic tape of size $c$, a tape whose initial content must be restored at the end of the computation. A central ingredient of their proof is the register program model. Namely, they constructed a uniform family of register programs that computes $x^n$ using $n$ registers and four accesses to $x$. Since then, determining the number of registers and input accesses required to compute a polynomial of a given degree has become a central question in the study of catalytic computation. On one hand, we prove that the four-access bound of Buhrman et al.\ is optimal: every passive-output register program computing a polynomial of degree greater than three requires at least four input accesses, independently of the number of registers. On the other hand, we show that their register bound is not optimal. For every $t\geq2$ and every field $K$ of characteristic $0$ or greater than $2t-1$, we construct a register program for $x^{2t-1}$ with four input accesses and $t$ registers. Our proofs rely on derivations and their exponential operators. This approach represents a register program as a series of exponential derivation operators, reducing register restoration to an operator identity. Finally, we use the uniform family of register programs to improve known trade-offs for catalytic streaming algorithms and register programs for matrix powering. The generalization of the lower-bound methods and the construction of the uniform family of register programs were developed with assistance from ChatGPT 5.6.

0.15

Möbius-Pseudorandomness for Algebraic Circuits

cs.CC math.NT ·2026-11-16 ·Gil Kalai, Mrinal Kumar, Ben Lee Volk
similarity 0.58
Abstract

We define a notion of Möbius-pseudorandomness for integer sequences generated by multivariate polynomials computed by small and simple algebraic circuits. This mirrors a related definition of Kalai that concerns boolean functions computed by small boolean circuits. We then prove Möbius-pseudorandomness results for polynomials computed by algebraic circuits with few multiplication gates (of any depth), for polynomials with small-dimensional partial derivative space, and for the determinant and permanent. We conjecture that these results hold in general for polynomial-size algebraic circuits.

0.39

Polar Switch: Fast Muon Orthogonalization with Polynomial Circuits

cs.LG math.NAmath.OC ·2026-10-19 ·Zhehang Du, Weijie Su
similarity 0.58
Abstract

Muon, a 2024-born optimizer for language models, differs from the 2015-born spectral gradient descent mainly in its fast, GPU-friendly Newton--Schulz polynomial for orthogonalizing the gradient matrix. Accordingly, a line of research proposes faster polynomial iterations for gradient orthogonalization, such as Polar Express and Gram Newton--Schulz, both built on quintic polynomials. In this paper, we introduce Polar Switch, a new approach to polynomial gradient orthogonalization. Using simple polynomial circuits, Polar Switch reaches a given high polynomial degree at a lower FLOP cost than quintic iterations. We define a circuit as a short sequence of symmetric matrix products on a few square buffers, and circuits with $k$ products form a restricted family of odd polynomials of degree up to $2^{k+1}+1$. We choose the sequence of products in each circuit, their coefficients, and how the circuits are composed by numerically minimizing a worst-case bound on the polar approximation error. This minimization is subject to a FLOP budget that accounts for symmetric matrix multiplication kernels and a rounding constraint for numerical stability in half precision. Our two recommended Polar Switch methods have 15.5--18.7\% lower runtime than Polar Express on square matrices and 8.6--16.2\% lower runtime than Gram Newton--Schulz on rectangular matrices with aspect ratios 3.25, 3.5, and 8, with comparable approximation accuracy. In pretraining Modded-NanoGPT \#91, Qwen3-0.6B, and Gemma 3-1B, Polar Switch reaches final validation losses similar to those of established orthogonalization methods. Across the more than 14 million matrices that each of the two recommended methods orthogonalized in these runs, the estimated output spectral norms never exceed the designed bounds by more than 3\%, demonstrating their numerical stability.

0.28