CS Paper Radar

Associativity of Multiplication Is Hard for Resolution

Vincent Liew

cs.CC cs.LO ·submitted 2026-10-06 18:46 UTC · v1
theorycode/data

Abstract

SAT solvers are empirically known to perform poorly when reasoning about multiplication. Yet for over a decade we have lacked a theoretical explanation for this phenomenon. CDCL SAT solvers implicitly search for resolution proofs, and no lower bound on proof size has ruled out the existence of short proofs that solvers simply fail to find. We give the first lower bound of this kind by showing that general resolution proofs of the associativity of $n$-bit multiplication require size $2^{Ω((n/\log n)^{1/4})}$. This lower bound holds for a broad class of multiplier encodings based on partial product summation, including the standard array and Wallace-tree multipliers used to bit-blast multiplication in SMT solvers. This result resolves an open problem of Beame and Liew. The proof constructs a reduction from a perfect-matching principle on bounded-degree bipartite expander graphs to multiplier associativity. Itsykson, Slabodkin, and Sokolov proved that this principle is hard for resolution. The lower bound for multiplier associativity follows. The same reduction, when combined with Håstad's recent lower bound for the perfect-matching principle of the odd grid, yields an exponential lower bound for multiplier associativity in the stronger bounded-depth Frege proof systems.

Comment
33 pages, 10 figures. Lean 4 formalization of the main theorems at https://github.com/dysfunctor/associativity

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

A Simple Algebraic Proof of the PCP Theorem

cs.CC ·2026-08-18 ·Prashanth Amireddy, Amik Raj Behera, Srikanth Srinivasan, Madhu Sudan, Sophus Valentin Willumsgaard
publishedtheory similarity 0.61
Abstract · Fixed an error in Lemma 3.3 and modified the tests accordingly

We give the simplest known algebraic proof of the PCP theorem, involving only ingredients like code concatenation, polynomial interpolation, and polynomial multiplication. Specifically, we prove that graph 3-coloring has a polynomial-sized proof that can be verified by a verifier tossing logarithmically many coins and querying a constant number of bits in the proof. In particular, our proof does not involve any PCP compositions; notably, it does not invoke the NP-completeness of any fixed problem, such as SAT or 3-coloring, in the construction of the verifier. The main innovation in our work is a clean, coding theoretic, way to encode univariate polynomials that allows us to implement ``low-degree testing'' using just a constant number of bits of queries. Insights from recent attempts to simplify the PCP proof by the authors (STOC 2026) and Goldreich (ECCC 2025) allow us to observe that low-degree was the key bottleneck in converting previous algebraic constructions of the PCP verifier into a constant query PCP. Thus, by overcoming this bottleneck, we get the full PCP verifier using elementary and self-contained steps. As concrete support for the claimed simplicity, we include the full pseudocode of the PCP verifier, assuming finite field arithmetic, and a full description of the completeness (aka ``honest'') prover, assuming multivariate polynomial arithmetic including interpolation and evaluation, that fit in about a page each.

0.32

Lower Bound of 22 for 3x3 Matrix Multiplication over the Integers

cs.CC ·2026-10-01 ·Isaac Rudich, Louis-Martin Rousseau
publishedtheory similarity 0.60
Abstract

Strassen showed that two 2x2 matrices can be multiplied with 7 multiplications instead of 8. Applied recursively, his algorithm multiplies two nxn matrices with O(n^2.807) multiplications, beating the naive O(n^3). The best known 3x3 recursive matrix multiplication algorithm uses 23 multiplications O(n^2.854). The best published lower bound of 21 (on algorithms with integer constants) leaves room for an algorithm with O(n^2.771) multiplications, and thus does not rule out the possibility of an algorithm that would beat Strassen's. We prove a lower bound of 22 multiplications for any 3x3 recursive algorithm with integer constants, proving that no such algorithm can do better than O(n^2.814) multiplications, and eliminating the possibility of a 3x3 algorithm that beats Strassen's 2x2 method. The proof builds on a recent decomposition method from Wang, who approached the problem by turning it into 496 subproblems. We provide exact solutions for 359 of them. The proof is in Lean; verification requires auditing only a few short files. The Lean formalization directly encodes statements about the limitations of recursive algorithms for matrix multiplication, as opposed to just a statement about the rank of the problem.

0.19

Deciding Scale Placement in MXFP4 Dot Products with Integer Arithmetic

cs.LO cs.ARcs.PL ·2026-10-21 ·Shreyas Vinayakumar
theory similarity 0.59
Abstract · 24 pages including references and two appendices, 1 figure, 5 tables

The Open Compute Project's microscaling (MX) family includes MXFP4, which stores 32 four-bit elements with a shared power-of-two scale. When lowering a dot-product reduction, a compiler can apply these scales before the reduction, or defer scaling until afterwards. Although equivalent over real numbers, these formulations can produce different IEEE binary32 results through overflow or underflow, with equivalence also depending on the reduction tree. We study the legality of compiler rewrites in either direction by deriving conditions under which the two formulations are bitwise equivalent. To decide rewrite legality, we construct an integer state machine that exploits the finite element alphabet and shared power-of-two scales, modeling overflow, NaN, and subnormal rounding. We prove its faithfulness under bounded scale codes and integer coefficients, yielding an exact encoding of the equivalence query in quantifier-free linear integer arithmetic (QF_LIA). For MXFP4, we derive a closed-form sufficient upper bound on the sum of scale exponents for any fixed binary reduction tree within the supported coefficient range. This bound depends on the size of the largest proper subtree. For four tree shapes at block lengths $k\in\{2,3,4,8,16,32\}$ and two shapes at $k=64$, SMT finds counterexamples when this upper bound is increased by one exponent step. Against the standard direct encoding in quantifier-free floating-point arithmetic (QF_FP), on matched queries cvc5 proves the integer version in seconds but reaches a configured one-CPU-hour limit on the floating-point proof even at $k=2$. The implementation was cross-checked using an independent floating-point encoding, exhaustive and stratified binary32 execution, and GPU replay of counterexamples. An MLIR lowering prototype demonstrates selection between the two formulations using the certified conditions as static or runtime guards.

0.24

Width-Bounded Equational Derivations for Finite Graph Expressions

cs.LO ·2026-09-08 ·Antonios Kalampakas
theory similarity 0.59
Abstract · 71 pages. Includes complete supplementary proofs. Reproducibility package: https://doi.org/10.5281/zenodo.22297410

Completeness of an equational presentation guarantees an equality path but need not control the resources used along it. For finite graph expressions we measure derivational space by the largest input-output interface of an intermediate raw term. For every finite doubly ranked edge alphabet $Σ$, we prove that equal closed expressions of pattern width at most $k$ are joined by a derivation in which every step applies an equation in either direction and every intermediate width is at most a computable $B_Σ(k)$, independently of graph size. The derivation uses only the structural magmoid laws and the fifteen finite-graphoid schemes. The construction compiles each expression through protected cores and finite routing windows to an encoding-canonical representative $\operatorname{NF}_k$ of width at most $4k+4$. We call this property bounded equational coherence. We also prove $\operatorname{bw}(F)\le\operatorname{patw}(F)\le4(\operatorname{tw}(F)+1)$ whenever the underlying simple graph has at least two edges, separate layered linear from branching expressions on cliques, and provide machine-checkable witnesses and finite invariants for the first five nontrivial clique values.

0.28

Upper and lower bounds on the OBDD-width of a special integer multiplication

cs.CC cs.DS ·2026-08-31 ·Tong Qin
similarity 0.58
Abstract · 11 pages, 1 figure

We consider the Boolean function ${\rm SMul}_{n-1}^n(\boldsymbol{x},\boldsymbol{y})$, which computes the middle bit of the multiplication of two natural numbers represented as $n$-bit binary strings $\boldsymbol{x}$ and $\boldsymbol{y}$, drawn from a restricted domain. We investigate the width of OBDDs computing ${\rm SMul}_{n-1}^n$. We introduce a combinatorially defined function $s_*(n)$ and show that the width of such OBDDs is $Θ(2^{s_*(n)})$.

0.23

Fast Evaluation of Polynomials with Rational Preprocessing

cs.DS ·2026-09-05 ·Thomas D. Ahle, Jakob B. T. Knudsen
theory similarity 0.58
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

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

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