Sumcheck optimization 2: Quasilinear Time and Square-Root Space old implementation

explanation for this equation:

\(\underbrace{p(r_1, …, r_i, x’)}_{x’\in\{0,1\}^{i-l}}= \sum\limits_{y\in \{0,1\}^l}\widetilde{eq}(r_1, …, r_i, x’,y)\cdot p(y)\)

\(=\sum\limits_{y\in \{0,1\}^l}\underbrace{\widetilde{eq}(r_1, …, r_i, y)}_{y\in \{0,1\}^{i}}\underbrace{\widetilde{eq}(x’,y)}_{y\in \{0,1\}^{l-i}}\cdot \underbrace{p(y)}_{y\in \{0,1\}^l}\)

\(=\sum\limits_{y\in \{0,1\}^i}\underbrace{\widetilde{eq}(r_1, …, r_i, y)}_{y\in \{0,1\}^{i}}\underbrace{\cdot p(y, x’)}_{y\in \{0,1\}^{i}}\)

Leave a Reply

Your email address will not be published. Required fields are marked *