CS Paper Radar

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

Aaron Sterling

cs.CC ·submitted 2026-10-13 21:46 UTC · v1
unusual

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.

Closest papers

Nearest neighbours by meaning across the whole index.

Partial Homogenization and the Structure of Optimal Algebraic Algorithms

cs.SC ·2026-11-17 ·Yuval Spiizer
theory similarity 0.59
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$.

0.50

Factor Closure in Noncommutative Algebraic Complexity

cs.CC ·2026-11-01 ·V. Arvind, Pushkar S. Joglekar
theory similarity 0.55
Abstract

We prove that $\VPnc$ is closed under taking factors over every field. If a noncommutative circuit of size $s$ computes a nonconstant polynomial of degree at most $D$, then each left or right factor has a circuit of size $O(sD^3)$. A central factor $g$ in a decomposition $f=agb$, with nonconstant outer factors $a,b$, has a circuit of size $O(sD^6)$. The proof uses a small weighted nondeterministic finite automaton (NFA) with replacement labels. Given $f=gh$, its labels depend on a word of maximum degree in $h$ and the coefficients of its suffixes. A pairing of accepting paths proves that the induced linear map $T$ satisfies $T(gh)=g$. Matrix substitution implements $T$ in a circuit. Applying the same substitution to a Boolean-sum verifier proves $\VNPnc$ closure. The construction also proves formula closure. The automaton has one copying state and, after leaving it, uses only scalar replacements. This structure gives formulas of size $O(s^2)$ for one-sided factors and $O(s^4)$ for central factors of a size-$s$ formula. The same map proves that polynomial-size noncommutative algebraic branching programs are closed under taking factors. Polynomial-size ABP factorizations over finite fields are already known from~\cite{AJ25}. These are arithmetic size bounds, with arbitrary field constants at unit cost, including over $\Q$. Over finite fields, combining the formula construction with~\cite{AJ22} gives randomized polynomial-time complete factorization of formula inputs, with factors output as formulas. For polynomial-degree circuit inputs, we obtain polynomial-length succinct ABP descriptions with polynomial-time edge queries. We also give two algorithms that output complete ordered irreducible factorizations as polynomial-size circuits: a deterministic $\FP^{\SigTwo}$ algorithm and a zero-error randomized algorithm with an NP oracle and expected polynomial running time.

0.29

Sunflowers of Reed--Solomon Codes

cs.IT math.CO ·2026-09-27 ·Roni Con, Anina Gruica, Maria Montanucci, Ferdinando Zullo
similarity 0.53
Abstract

We introduce and study Reed--Solomon sunflowers, namely families of Reed--Solomon codes whose pairwise intersections are all equal to the same fixed subspace. This notion lies at the intersection of extremal subspace combinatorics and coding theory: it can be viewed as a structured version of the sunflower problem in the Grassmannian, and it naturally produces constant-dimension subspace codes with prescribed minimum distance. We focus mainly on the case in which the center is the one-dimensional space generated by the all-one vector. We give an algebraic criterion, expressed in terms of generalized $V$-matrices, ensuring that a family of Reed--Solomon codes forms such a sunflower. We then study the size of these families through counting and constructions. In dimension two, we show that all distinct Reed--Solomon codes form a sunflower and determine its size by counting Reed--Solomon codes up to affine equivalence of their evaluation vectors. For fixed dimension $k\geq3$ and length $\ell\geq2k-1$, we give an explicit recursive construction with $Ω_{k,\ell}(q^{\lfloor\ell/(2k-1)\rfloor})$ petals and a greedy existence argument with $Ω_{k,\ell}(q^{\ell-2k+2})$ petals as $q\to\infty$. We also apply the greedy argument to obtain families of $[\ell,k]_q$ MDS codes of size $Ω_{k,\ell}(q^{2(\ell-2k+2)})$, whose pairwise intersections have dimension at most one but need not be equal.

0.17

Entrywise Logarithmic Matrix Algebra and Dichotomy of Planar Graph Homomorphisms

cs.CC ·2026-09-30 ·Jin-Yi Cai, Zhuxiao Tang
theory similarity 0.53
Abstract · 93 pages, 6 figures

We prove a complexity classification of counting planar graph homomorphisms with non-negative weights. For a real symmetric matrix $M$ with nonnegative entries, the problem $\GH(M)$ is either (1) P-time computable over all graphs, or (2) \#P-hard in general but P-time computable over planar graphs, or (3) \#P-hard over planar graphs. Furthermore, $\GH(M)$ in (2) consists of precisely those that involve the P-time FKT algorithm to count planar perfect matchings with a holographic transformation. The dichotomy for entrywise positive and full rank matrices lies at the core of the proof. In this setting, the main tool is a matrix algebra ${A}$ (a vector space with bilinear multiplication) formed by taking the real span of (centered) entrywise logarithms of all realizable matrices from $M$ using planar edge gadgets and polynomial interpolation. We then define a multiplicative homomorphism $F(\cdot)$ on the algebra ${A}$, which turns out to be a polynomial map. The exponents of prime factorization of component polynomials of $F$ induce graph distances for distance-regular graphs. These graphs are either the Hamming graphs or Doob graphs using a classification result for distance-regular graphs (if $\PlGH(M)$ is not \#P-hard), after obtaining their intersection numbers. The dichotomy is proved in either case. We then extend the complexity classification to all nonnegative matrices.

0.38

A Dichotomy for Exact Quantum Circuit Amplitudes

cs.CC ·2026-11-17 ·Chenghua Liu, Boning Meng
similarity 0.53
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

Automatic constraints with few subpowers and graphoid recognition

cs.LO cs.FL ·2026-09-07 ·Antonios Kalampakas
theory similarity 0.53
Abstract · 23 pages, 2 figures. Reproducibility package: https://doi.org/10.5281/zenodo.22648283

Finite automata can describe relations of unbounded arity that are exponentially larger than their descriptions. We prove that constraint satisfaction for such relations is solvable in polynomial time whenever their length slices are preserved by a common fixed edge operation on a finite domain. The algorithm computes compact representations of the complete solution relation and its projections. Its main ingredient is a polynomial-time compilation of nondeterministic finite automata into the fork witnesses and small projections required by the few-subpowers algorithm. In the Mal'tsev case, a direct proof is polynomial also when the domain and operation table are supplied as input, answering the Mal'tsev tractability question for automatic constraint satisfaction. We also characterize all invariant relations of a family of 3-edge algebras with neither Mal'tsev nor near-unanimity terms. Their normal forms combine Boolean activity constraints with affine value spaces and yield canonical quadratic-bit representations constructible from NFAs or arbitrary generators. For graphoid automata, these results give polynomial-time recognition without a graph-width restriction, effective boundary composition, and comparison of finite graph relations. The quadratic boundary bounds are optimal in the worst case. A fixed three-state example separates polynomial-time recognition from hard exact counting.

0.42

Group Action and Spin Representation Lead to a Holant* Complexity Dichotomy on Domain Size 3

cs.CC ·2026-10-03 ·Jin-Yi Cai, Jin Soo Ihm
theory similarity 0.52
Abstract

We prove a complexity dichotomy theorem for $\mathrm{Holant}^*$ problems over complex-valued symmetric constraint functions $\mathcal{F}$ on domain size $3$. We give a decidable tractability criterion and prove that if $\mathcal{F}$ satisfies the criterion, then $\mathrm{Holant}^*(\mathcal{F})$ is solvable in polynomial time, and otherwise it is #P-hard. This is the first Holant dichotomy for a set of complex-valued constraint functions on higher domains. We show that complex-valued constraint functions have a rich structure not observed in real-valued constraint functions. This structure is only revealed when we analyze them in a bipartite Holant setting with a non-standard bilinear form and provides the backbone to the proof of the dichotomy. We use group actions and the spin representation of $\mathrm{SL}(2, \mathbb{C})$ in $\mathrm{SO}(3, \mathbb{C})$ and the generalized orthogonal group to facilitate this analysis. We also introduce $\textit{frames}$ and $\textit{shells}$. Frames linearize the group action and provide a unified framework for proving #P-hardness when used in conjunction with shells. Furthermore, we characterize the lower dimensional constraint functions by $\textit{annihilators}$, which makes it possible to analyze $\textit{essentially Boolean domain}$ functions in domain size $3$.

0.18

Ramanujan quantum expanders from the Weil representation

cs.CC quant-ph ·2026-09-29 ·Siddhartha Jain
similarity 0.51
Abstract

For every odd prime power $q$ and $D=q+1$, we construct an infinite family of Ramanujan quantum expanders of degree $D$. The construction transfers Morgenstern's Ramanujan Cayley graphs on $\operatorname{PSL}_2(\mathbb{F}_{p})$ for $p$ which is an even power of $q$, through the odd irreducible subrepresentation of the Weil representation of $\operatorname{SL}_2(\mathbb{F}_{p})$. For a quantum expander of dimension $N$, our implementation uses $O(\log^2 N)$ elementary gates, and $O(\log N)$ ancilla qudits, using a fixed finite gate set depending on $q$. An advantage compared to the previous work of Iyer, Jain, Jordan, and Somma (FOCS 2026) is that assuming the quantum circuit is implemented exactly, we satisfy the $2\sqrt{D-1}/D$ singular value bound exactly without any additive error.

0.27