$\newcommand{\zero}{\color{red}{\alpha}}$ $\newcommand{\one}{\color{lightgreen}{\beta}}$ $\newcommand{\xzero}[1]{\color{grey}{(1 - #1)}}$ $\newcommand{\xone}[1]{\color{grey}{#1}}$ $\def\stackbelow#1#2{\underset{\displaystyle\overset{\displaystyle\shortparallel}{#2}}{#1}}$ Background In late 2023, Justin Thaler posted a paper on optimized sumcheck for fields of small characteristics. Having experience with low-level hardware-optimized modular multiplication, Yuval Domb began exploring ways to further optimize Justin's results using his extensive knowledge of efficient multiplication techniques. He wondered if the Karatsuba algorithm could be applied to reduce the number of base-field multiplications in Justin's optimized sumcheck prover algorithm (referred to as Algorithm 3 in the paper). The Karatsuba algorithm reduces the number of multiplications needed for two large integers from four to three, offering a 25% improvement. While this may seem modest, Justin helped us see that even small improvements are significant in the context of the sumcheck protocol over smaller fields. This is particularly relevant as commitment schemes like the one in Binius have become so efficient that the sumcheck protocol could become a bottleneck in SNARKs. Thus, we focused on incorporating the Karatsuba algorithm into Justin's Algorithm 3 for the case when the sumcheck polynomial degree is $d = 2$. The two main challenges were: For the $d = 2$ case, how do we apply the Karatsuba algorithm across multiple rounds of the sumcheck protocol? If we solve the first challenge, how do we generalize the Karatsuba algorithm to any degree $d > 2$?

The Kate commitment scheme can be used prove the knowledge of a bunch of polynomials by "opening" all of them at a single scalar. Suppose we have the following polynomials to be opened at respective points (we're considering a fairly general case here): Polynomials Opening points $f_{1,1}, f_{1,2}, \dots, f_{1,m}$ $z_1$ $f_{2,1}, f_{2,2}, \dots, f_{2,m}$ $z_2$