Space-time constraints
\def\F{\mathbb F}
Goal. Simulate a form of (random access) memory using bivariate polynomials P\in\F[X,Y].
Intuitively, we lay out the memory with time on the X axis and space (addresses) on the Y axis.
Stack
Start with a simple stack where P(𝜔_n^i, 𝜔_m^j) is the value of stack location j at time i.
The initial polynomial is the zero polynomial on our basis 𝜔^j
P(0, Y) = Y^m - 1
Note. It looks like we can handle the memory sparsely, both in the polyonmial form and in the merkle trees.
L_{m,j}(Y) = \frac{𝜔_m^j}{m} \frac{Y^m - 1}{Y-𝜔_m^j}
Push & Pop
Constraint. (Push). Rotate all elements to the right, add an element x. Has the following constraints:
\begin{aligned} P(X, 𝜔_m^{m-1}) &= 0 \\ P(𝜔_n ⋅ X, Y) &= P(X, 𝜔_m ⋅ Y) + x ⋅ L_0(Y) \end{aligned}
Constraint. (Pop). Operate the push constraint in reverse.
Random access
Constraint. (Compare and swap). Replace the value at j from a to b.
\begin{aligned} P(X, 𝜔_m^j) &= a \\ P(𝜔_n ⋅ X, Y) &= P(X, Y) + (b - a) ⋅ L_j(Y) \end{aligned}
The problem here is that we need to encode the j somehow, either in a precomputed polynomial or as a column. Since all usage of j will be in the form 𝜔_m^j we will use that instead. the final constraint will look like:
\begin{aligned} P(X, Q(X)) &= a \\ P(𝜔_n ⋅ X, Y) &= P(X, Y) + (b - a) ⋅ \frac{Q(X)}{m} \frac{Y^m - 1}{Y-Q(X)} \end{aligned}
To do. What if Q(X) is not of the form 𝜔_m^j?
The first constraint has a degree bound of (\deg P)⋅(\deg Q) = n^2 m. So far we have only handle constant constraint bounds. How do we LDE test this efficiently?
We could add a temporary value? t = Q(X), P(X, t) = a?
In addition, to force Q(X) to be a root of unity, we can add a constraint
Q(X)^m = 1
which has degree bound m\deg Q = nm. Again, how do we LDE-test this efficiently?
Polynomial composition
Both approaches above hit the problem that we need to low-degree-test an expression of the form P(Q(X)). The straightforward approach has degree bound (\deg P)(\deg Q) which is quadratic. This will kill prover performance and more than double proof size.
Goal. Find a way to LDE test polynomial compositions efficiently.
To do. Specify goal more concretely.
https://en.wikipedia.org/wiki/Polynomial_decomposition
https://www.math.mcgill.ca/rickards/PDFs/amer.math.monthly.118.04.358-rickards.pdf
https://www.cs.cornell.edu/~kozen/Papers/poly.pdf
Chebyshev polynomials have the nesting property T_n(T_m(X)) = T_{mn}(X).
https://dspace.mit.edu/bitstream/handle/1721.1/71792/Kedlaya-2011-FAST%20POLYNOMIAL%20FACT.pdf?sequence=1&isAllowed=y https://www.cse.iitk.ac.in/users/nitin/courses/CS681-2016-17-II/pdfs/slides-dwivedi.pdf Evaluates f(g(x)) \mod h(x) in less then \mathcal O(n^2) time using FFTs. => Read. http://users.cms.caltech.edu/~umans/papers/U07.pdf
https://www.cse.iitk.ac.in/users/nitin/courses/CS681-2016-17-II/pdfs/slides-dwivedi.pdf
https://citeseer.ist.psu.edu/viewdoc/download;jsessionid=611B98690C1028968AED2736F9E1E77C?doi=10.1.1.51.3154&rep=rep1&type=pdf
https://arxiv.org/pdf/0807.3578.pdf
Aside: https://en.wikipedia.org/wiki/Bruun's_FFT_algorithm
