Suppose there is an oracle $\mathcal{O}$ that computes a tiny fraction of the entries of the product of two uniformly random binary matrices over integers. We prove that there is a nearly linear-size randomized $\mathcal{O}$-oracle circuit that, with high probability, computes all the entries of the product of every pair of binary matrices. This extends the previous ``worst-case exact to average-case approximate'' reduction of Hirahara and Shimizu (STOC 2025), which assumes the average-case distribution to be uniformly random matrices over a finite field, to uniformly random binary matrices.

The technical core of our reduction is an approximate list-decoding procedure for a signed sum encoding of the matrix product over the integers based on expander walks. To decode this encoding, we combine the near-linear-time approximation algorithm for MAX $k$-CSP supported on splittable tuples by Jeronimo (RANDOM 2023) with the XOR lemma for multi-output functions by Hirahara and Shimizu (STOC 2025).