CS Paper Radar

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

Gregory Morse

cs.CC cs.DS ·submitted 2026-08-31 04:45 UTC · v1
theorycode/data

Abstract

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.

Comment
25 pages, 1 table. Complete Lean 4 formalization and verification artifacts: https://github.com/GregoryMorse/unrestricted-boolean-mul

Closest papers

Nearest neighbours by meaning across the whole index.

The multiplicative complexity of the three-bit low-half multiplier

cs.CC cs.LOmath.CO ·2026-11-11 ·Bshara Alhodali, Gregory Morse
theory similarity 0.69
Abstract · 21 pages, 1 table. The Lean 4 formalization and verification artifacts are linked in the paper (Appendix A)

We prove that the multiplicative complexity of the three-bit low-half multiplier is six, giving a structural, enumeration-free lower-bound proof valid against unrestricted nonlinear reuse in Boolean XOR-AND circuits. The value was first established by SAT searches of the first author and independently confirmed by the second author. An explicit six-AND circuit supplies the upper bound. The lower bound combines derivatives, quadratic products, complementary minors, and extraction modulo a Boolean ideal. Independent finite checks accompany the arguments. $\mathrm{MC}(M_3)=6$ is fully formalized in Lean 4, using only Lean's three standard axioms (propositional extensionality, choice and quotient soundness).

0.18

Fast Evaluation of Polynomials with Rational Preprocessing

cs.DS ·2026-09-05 ·Thomas D. Ahle, Jakob B. T. Knudsen
theory similarity 0.66
Abstract

Horner's rule evaluates a monic degree-$n$ polynomial using $n-1$ multiplications. We show that with rational preprocessing of the coefficients, any such polynomial can be evaluated using only $\lfloor n/2 \rfloor + 1$ multiplications over fields of characteristic zero or of characteristic $p>n$. This resolves the multiplication side of a conjecture of Rabin and Winograd (Comm. Pure Appl. Math 1972), who achieved $n/2 + 2\lceil\log_2 n\rceil$ multiplications and conjectured the logarithmic overhead was necessary. We show that this multiplication count can't be beaten in general, proving that three multiplications do not suffice for degree~$6$. This strengthens the lower bound of Pan (STOC 1978), who proved a tight bound for general, complex preprocessing. In characteristic~2, for every $n>1$ and every finite field of size at least $2n$, we prove that an $n$-multiplication chain cannot parametrize all value vectors at $2n$ distinct evaluation points, even with arbitrary preprocessing. We give $\lfloor n/2 \rfloor + 1$ multiplication schedules over characteristic~2, each with an explicit inverse, for every odd degree $n\le 25$ and conjecture that this is possible for all $n$. We also give an injective polynomial construction for universal hashing that uses $N$ multiplications to hash $2N$ values with a single random key. This improves the best previous construction by Daniel J. Bernstein (cryp.to).

0.09

Exponential Correlation Bounds for Polynomials

cs.CC ·2026-09-23 ·Eshan Chattopadhyay, Pooya Hatami, Chin Ho Lee, Shachar Lovett, Avishay Tal +1 more
publishedtheoryhighly cited similarity 0.61
Abstract · 26 pages. Revision: Generalized the main results to all fields, added new applications and improved some existing ones, and expanded the exp…

We prove that the XOR of $k$ majorities on disjoint blocks of $\ell$ bits has correlation at most $(4d/\sqrt{\ell})^k$ with every Boolean-valued degree-$d$ polynomial over an arbitrary field. By known techniques, we obtain explicit pseudorandom generators that fool such polynomials on $n$ Boolean inputs with seed length $d^2\cdot\polylog(n/\varepsilon)$. The correlation and the generator extend to small $\mathsf{AC}^0[q]$ circuits, for every fixed prime power $q$. These results resolve several long-standing questions in circuit complexity and pseudorandomness.

0.61

Exact Quantum Query Complexity of the Five-Bit Symmetric Boolean Function $\Exact^5_{3,4}$

cs.CC quant-ph ·2026-10-17 ·Guoliang Xu, Haoran Zhang, Mengfan Wu, Songyao Xue, Mingke Liu
theory similarity 0.60
Abstract

Let \(f = \text{EXACT}^5_{3,4}\) be the Boolean function that equals 1 exactly on inputs of Hamming weight 3 or 4. Earlier numerical studies reported success probabilities close to one using three queries, but the existence of an exact three-query algorithm had remained unresolved. This paper settles this problem by proving that the exact quantum query complexity of \(f\) is \(4\). For the lower bound, we express every three-query algorithm through layer-by-layer Gram matrices of low-degree Fourier coefficients. We then construct a fixed rational dual certificate whose slack matrices are all positive definite. This certificate separates the necessary Gram-matrix region from the exact-output condition and therefore rules out every exact algorithm using at most three queries in the stated model. The positivity verification reduces to five small rational matrices and Sylvester's criterion. For the upper bound, we invoke the previously known four-query algorithm for the seven-bit function \(\text{EXACT}^7_{3,4}\) and apply the standard padding reduction. To quantify the near-exact behavior, we use the same certificate to derive a valid, though not claimed tight, lower bound \(\frac{25600}{43779488192449}>0\) on the worst-case error of every algorithm using at most three queries. This positive error gap is compatible with the near-unit success probabilities reported in earlier numerical studies, which do not establish exact computation.

0.06

Generic Characteristic-Zero Equivalence Between Derivative Bézout Inversion and Multipoint Evaluation

cs.SC cs.LG ·2026-08-28 ·Zijian Zeng
theory similarity 0.59
Abstract

Let $a_1,\ldots,a_m$ be distinct elements of a field $K$, and let $Z(X)=\prod_{i=1}^m (X-a_i)$. We study the arithmetic complexity of computing the unique normalized Bezout pair $s,t$ satisfying $sZ+tZ'=1$, with $°t<m$ and $°s<m-1$. The classical product-tree approach requires $O(M_K(m)\log m)$ field operations, where $M_K(m)$ denotes the cost of multiplying degree-$<m$ polynomials over $K$. Thus, even when $M_K(m)=O(m\log m)$, the resulting bound is $O(m\log^2 m)$ rather than $O(m\log m)$. Over an infinite field of characteristic zero, we prove that, in the generic rational straight-line-program model, computing all coefficients of the canonical Bezout pair is equivalent, up to an additive $O(M_K(m))$ cost, to arbitrary-node multipoint polynomial evaluation and to interpolation. The main ingredient is an explicit differential reconstruction that recovers $Z$ from $(s,t)$ in $O(M_K(m))$ arithmetic operations on a nonempty Zariski-open subset. Combining this reconstruction with automatic differentiation and transposition yields the complexity equivalence. We further transfer Strassen's lower bound for the elementary symmetric functions to the Bezout problem, obtaining an $Ω(m\log m)$ nonscalar lower bound. Hence an $O(m\log m)$ algorithm, if it exists in this model, would be asymptotically optimal. The reconstruction is genuinely characteristic-dependent: in characteristic $p$, all squarefree polynomials $X^p+cX+d$, with fixed $c\ne 0$, have the same normalized Bezout pair $(0,c^{-1})$. Therefore the all-field, all-input $O(m\log m)$ problem remains open; generically in characteristic zero, however, it is reduced to the corresponding arbitrary-node multipoint evaluation and interpolation problem.

0.22

Deterministic NC Quadratic Root Counting in Characteristic Two

cs.CC ·2026-09-11 ·Sanyam Agarwal, Gorav Jindal
similarity 0.59
Abstract

Counting satisfying assignments of Boolean formulas is a basic problem in theoretical computer science, with $\#3\text{-}\SAT$ as the standard $\SharpP$-complete problem. More generally, counting the solutions of a system of polynomial equations over $\F_2$ is $\SharpP$-complete. Here we focus on the more structured problem of counting the solutions of a single polynomial equation. For polynomial equations over finite fields, Ehrenfeucht and Karpinski \cite{computationalcomplexityofxorandcountingproblems1990} showed a sharp difference between degrees two and three: quadratic root counting is solvable in polynomial time, while the degree-three problem is $\SharpP$-complete. Their quadratic algorithm is sequential. For fixed finite fields, Ishai et al.~\cite{ishai2012randomizing} later gave deterministic parallel algorithms in odd characteristic and randomized parallel algorithms in characteristic two. We give a deterministic $\NC$ algorithm for exactly counting the solutions of a quadratic polynomial equation over every fixed finite field of characteristic two. Our algorithm separates the radical and uses the absolute trace to realize the bit distinguishing the two nondegenerate finite-field types as the Arf invariant \cite{arf1941untersuchungen} of a quadratic form over $\F_2$. It then recovers that invariant from an integral matrix using Browder's determinant criterion \cite{browder2006complete}. This replaces the randomized canonical-form step in the algorithm of Ishai et al.

0.18

Vanishing Ideals and the Computational Tractability of Sum-of-Squares over Boolean Domains

cs.DS ·2026-09-29 ·Monaldo Mastrolilli
theory similarity 0.59
Abstract

Building on the bit-complexity framework of Raghavendra-Weitz and the moment-SOS criteria of Gribling-Polak-Slot, we study the effective use of truncated vanishing identities over Boolean polynomial systems. A complete, constructible identity space gives an augmented moment SDP that can be optimized with exact rational feasibility and arbitrary additive accuracy. We give a self-contained geometric implementation: an explicit affine reduction and a simplex of Boolean evaluations supply the radius bounds required by rational ellipsoids. The identity space can be constructed directly or extracted from a supplied graded Groebner basis, including one supplied at a higher truncation degree. An explicit transfer theorem connects this augmented formulation to the original system. Two-sided SoS derivations eliminate the added equality axioms from certificates, with controlled degree and coefficient growth, and imply containment of a projected higher-level moment relaxation in the augmented body. Together with spectral coefficient bounds, this gives polynomial-time search for rational proofs with an additive perturbation. For Min-closed linear systems, propagation constructs the identity space in polynomial time at fixed degree and gives degree-(4t+4) certificates for both signs of each degree-t basis element. Consequently, a rational degree-(8d+4) proof of f + epsilon >= 0 can be found in polynomial time for fixed d whenever f >= 0 has a degree-2d proof. The augmented degree-2d moment SDP can be optimized in polynomial time with exact rational feasibility and a comparison to the original degree-(8d+4) relaxation. Boolean complementation gives the same results for Max-closed systems, including generalized packing and covering. Min-closed systems thus provide a concrete application of the general criteria. All complexity bounds are in the Turing model.

0.42

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.49