A Deterministic Algorithm for Minimum Witness Convolution Below the Three-Halves Exponent

Abstract

Given two length-n Boolean arrays, minimum witness convolution asks, for each output position k, for the least index i with A[i]B[k − i] = 1. We give a deterministic algorithm taking Õ(n1.49644) time, and therefore O(n1.49645) time, on a word RAM with O(log n)-bit words. The construction builds on the integer thin-product framework of Alman and Vassilevska Williams (arXiv:2610.06783v1). We modify its tensor encoding circuit by storing only high-order leaves. Two separate three-term linear identities recover each omitted leaf’s factors before their product is formed. This preserves the query bound while absorbing the encoding cost into box preprocessing. We then encode block convolutions by polynomial residues, evaluate them over a prime field through ordinary integer-product instances, and interpolate only the requested entries. An ordered refinement procedure uses these exact counts to locate the minimum witness. Each refinement level uses its own inner dimension and an exactly chosen switching order. Uniform estimates, together with rational interval certificates for the numerical constants, establish the stated exponent at every level. The algorithm is correct on every input and uses no randomization.