Input Relation:

$${\mathcal{R}}_{\Sigma ,{\mathbb{H}}_k,\vec{d}}:=\left\{\left(f(X_1,\dots ,X_k),\sigma \right)\mid \sigma =\sum _{\vec{x}\in {\mathbb{H}}_k}f(\vec{x})\wedge \forall i.d_i={\mathrm{deg}}_{X_i}(f)\right\}$$

Output Relation:

$${\mathcal{R}}_{\Sigma ,{\mathbb{H}}_{k-1},\vec{d}}:=\left\{\left(f(X_1,\dots ,X_{k-1}),\sigma \right)\mid \sigma =\sum _{\vec{x}\in {\mathbb{H}}_{k-1}}f(\vec{x})\wedge \forall i.d_i={\mathrm{deg}}_{X_i}(f)\right\}$$

Reduction:

1. Prover computes: