- number of gates on a layer is S
- number of bits for that layer is $s = log S$
- number of variables in poly we sum is $f(b, c)$ where $|b| = s$ and $|c| = s$
- so total number of variables = $2s$
- prover time for sumcheck is $O(2^v)$
- #todo show how thalers prover time got to this
- $O(2^v \cdot T - T) = O(2^v)$
- then $\sum_{i} 2^{v-1} = 2^v - 1$
- linear time sumcheck for multilinear functions
- evaluation form representation of the polynomial
- get the halves and sum to get the round message
- get the r
- fold using r
- repeat
- basic stuff
- linear time sumcheck for product of multilinear functions
- similar to regular sumcheck over multilinear functions
- but now returns round poly in {0, 1, 2}
- and two bookkeeping tables

- linear time sumcheck for gkr functions
- gkr functions are of the following form
- $\sum_{x, y \in \{0, 1\}^l} f_1(g, x, y) \cdot f_2(x) \cdot f_3(y)$
- where $f_1$ represents a sparse polynomial i.e $O(2^l)$ non-zero elements out of the possible $O(2^{3l})$
- libra achieves linear time by rewriting the equation above
- $\sum_{x, y \in \{0, 1\}^l} f_1(g, x, y) \cdot f_2(x) \cdot f_3(y)$ = $\sum_{x \in \{0,1\}^l} f_2(x) \sum_{y \in \{0,1\}^l} f_1(g, x, y) \cdot f_3(y)$ = $\sum_{x \in \{0,1\}^l} f_2(x) h_g(x)$
- where $h_g(x) = \sum_{y \in \{0,1\}^l} f_1(g, x, y) \cdot f_3(y)$
- so the equation $\sum_{x \in \{0,1\}^l} f_2(x)h_g(x)$ is only in terms of x
- this is exactly the same as performing sumcheck over the product of two multilinear polynomials
- the only thing missing is generating the book-keeping table for $h_g(x)$
- the book-keeping table for $f_2(x)$ is already known as the polynomial was gotten from the multilinear extension of some array.

- detour
- if I have some multilinear function $f(a, b, c)$
- I can interpret this in the lagrange basis
- a dot product between the evaluation form values and the bit checkers for each evaluation form value.
- i.e $f(a, b, c) = \sum_{x, y, z \in \{0,1\}^l} eq_{xyz}(a, b, c) \cdot F[x, y, z]$
- where F is the array that defines the multilinear form array representation of $f$
- only the non-zero elements in F will contribute to the sum
- if we knew all the locations of F that were non-zero can we optimize this computation?
- imagine we had a mapping (a, b, c) -> non_zero_ouptut
- let us call this mapping $N$
- we can use this to compute the final output
- $\sum_{(x, y, z) \in N} eq_{xyz}(a, b, c) \cdot F[x, y, z]$
- this will give the same answer, but reduces the amount of computations we are required to do (drastically if F is sparse).

- can eq be decomposed?
- seems we indeed can, we can express a big eq equation as a product of smaller eq equations
- $eq(x_1, x_2, x_3, y_1, y_2, y_3) = \prod_{i = 1} (1 - x_i)(1 - y_i) + x_i \cdot y_i$
- each product term is an eq for $x_i$ and $y_i$
- hence we can rewrite as follows
- $eq(x_1, x_2, x_3, y_1, y_2, y_3) = eq(x_1, y_1) \cdot eq(x_2, y_2) \cdot eq(x_3, y_3)$

- idea summary
- it is assumed one has a sparse function, where the non-zero entries are know i.e both index and non-zero output.
- we have some equation that uses the sparse function as a multiplication term.
- knowing the zero / non-zero entries of this function makes computing that equation a lot more efficient, because you only look at the non-zero terms.
- hence this means that you need to keep the sparse function in the lagrange basis.
- that way, you know what is 0 and you can avoid doing wasted computations.

- generating the book-keeping table $A_{h_g}$
- we need a table that evaluates $h_g(x)$ over the boolean hypercube.
- recall $h_g(x) = \sum_{y \in \{0, 1\}^l} f_1(g, x, y)f_3(y)$
- here $f_1$ is partially evaluated at g, our sparse entries are no longer valid
- to keep it sparse, we can extract $g$ into it's own eq
- $h_g(x) = \sum_{z, y \in \{0, 1\}^l} eq(g, z) \cdot f_1(z, x, y) \cdot f_3(y)$
- now given any x we should be able to compute the corresponding value of $h_g(x)$
- we have the map (a, b, c) -> non_zero
- the value of x we want to evaluate $h_g(x)$ is known and it is also boolean
- so we can filter the map based on $b == x$
- let us call this filtered map $N_x$
- the final equation becomes
- $h_g(x) = \sum_{(z, y) \in N_x} eq(g, z) \cdot F_i[z, x, y] \cdot f_3(y)$
- the above is computable without ever needing to compute the full $f_1$ table

- after running sumcheck on $\sum_{x \in \{0,1\}^l} f_2(x)h_g(x)$
- we'd have randomness associated with x, let us call this u.
- going to back to the original equal we can replace all x with u to give
- $\sum_{y \in \{0, 1\}^l} f_1(g, u, y)f_2(u)f_3(y)$
- $f_2(u)$ will be a scalar, we can do scalar mul with all entries in $f_3(y)$ and that gives us the book-keeping table
- we also need a book-keeping table for $f_1(g, u, y)$ we want to get that table without constructing the entire $f_1$ table and then partially evaluating at g and u
- we can use the same idea, keep $f_1$ in the lagrange basis, we get
- $\sum_{x, y, z \in \{0, 1\}^l} eq(g, z) \cdot eq(u, x) \cdot F[z, x, y] \cdot f_2(u) \cdot f_3(y)$
- now that F is entirely in the lagrange basis and we also know all the non-zero entries we can make the computation compute the $A_{f_1}$ table efficiently.
- $A_{f_1}[y]$ = $\sum_{x, z \in \{0, 1\}^l} eq(g, z) \cdot eq(u,x) \cdot F[z, x, y]$
- let $N$ be the mapping of all entries in $f_1$ that are non-zero
- given that we know y we can filter that mapping to get $N_y$
- $A_{f_1}[y] = \sum_{(x, z) \in N_y} eq(g, z) \cdot eq(u, x) \cdot F[z, x, y]$
- but this is much faster to compute

- see [[generalize-libra-sumcheck-to-c-phases]]

- 2 to 1 trick
- initially we have $\sum f(g, x, y) \cdot f_2(x) \cdot f_3(y)$
- at the folding step we have two different evaluations of g i.e $g_1$ and $g_2$
- $c_1 = \sum f(g_1, x, y) \cdot f_2(x) \cdot f_3(y)$ and
- $c_2 = \sum f(g_2, x, y) \cdot f_2(x) \cdot f_3(y)$
- rather than performing two libra sumchecks we want to perform just one
- we can perform this reduction via the [[random-linear-combination]]
- LHS
- $C = \alpha \cdot c_1 + \beta \cdot c_2$
- RHS
- $\alpha \cdot f(g_1, x, y) \cdot f_2(x) \cdot f_3(y) + \beta \cdot f(g_1, x, y) \cdot f_2(x) \cdot f_3(y)$
- we can factorize $f_2(x)$ and $f_3(y)$
- $(\alpha \cdot f(g_1, x, y) + \beta \cdot f(g_2, x, y)) \cdot f_2(x) \cdot f_3(y)$
- we can further simplify the sum via $I(g,z)$
- $((\alpha \cdot I(g_1, z) \cdot f(z, x, y)) + (\beta \cdot I(g_2, z) \cdot f(z, x, y)) \cdot f_2(x) \cdot f_3(y)$
- which allows us to factor out $f(z, x, y)$
- $(\alpha \cdot I(g_1, z) + \beta \cdot I(g_2, z)) \cdot f(z, x, y) \cdot f_2(x) \cdot f_3(y)$
- hence the only change to account for folding is the building of the $I(g, z)$ table