Chapter 1: Algorithms for Sumcheck Parallelization
Abstract: In this chapter, we explore sum-check protocols from the point of view of parallelizable computation in devices such as GPUs. We explore algorithmic modifications to the sum-check protocol, for products of Multi-Linear Extensions (MLE) to improve parallel compute and address memory bottlenecks.
Paper: https://github.com/ingonyama-zk/papers/blob/main/sumcheck_201_chapter_1.pdf
Code: https://github.com/ingonyama-zk/super-sumcheck
Super-sumcheck is aimed at exploring algorithmic improvements to the sumcheck prover to run it in a fully parallelizable and memory-efficient manner. We implement two algorithms for running sumcheck prover for arbitrary statements in MLE polynomials (read the full description here):
Algorithm 1: Collapsing arrays
Algorithm 2: Precomputations
Highlights: Super-sumcheck enables running sumcheck prover for any "gate" equation in MLE polynomials and hence provides a proof-system and arithmetisation agnostic sumcheck prover backend. The two algorithms fall in different ends of the performance spectrum, algorithm 1 is less-memory intensive but consumes more computation cycles, algorithm 2 is memory intensive but allows offloading lot of work to pre-computation.
