Currently, we're computing the Lagrange coefficients of round univariates faithfully evaluating our subrelations at $(x_{<k}, 0, i_{>k})$. However, the evaluation of round univariate at 0 can be derived as
-
$\texttt{target\ sum} - S_0(1)$ in round $0$
-
$S_{k-1}(u_{k-1}) - S_k(1)$ in round $k$,
which should save us ~1/MAX_PARTIAL_RELATION_LENGTH of total sumcheck prover work.
The solution might be to redefine extended edges as univariates in the {1, ..., MAX_PARTIAL_RELATION_LENGTH-1} basis, and prepend the eval at zero after combining the round subrelation accumulators.
Currently, we're computing the Lagrange coefficients of round univariates faithfully evaluating our subrelations at$(x_{<k}, 0, i_{>k})$ . However, the evaluation of round univariate at 0 can be derived as
which should save us ~1/
MAX_PARTIAL_RELATION_LENGTHof total sumcheck prover work.The solution might be to redefine extended edges as univariates in the {1, ...,
MAX_PARTIAL_RELATION_LENGTH-1} basis, and prepend the eval at zero after combining the round subrelation accumulators.