following previous posts: 1,2,3,4
An \(O(n)\)-sized circuit for evaluating \(\widetilde{M}\)
talking about this circuit:
notes:
- for witness: \(row, col, val\) are enough to describe a multilinear extension \(\widetilde{M}\)
- \(e_{row}, e_{col}\) should be the evaluations
I need recap on Offline memory checking
let’s follow this post to continue
I think this two query vector can represent a matrix:
\(\begin{bmatrix}1&0&1&0&0&0&0&0\\1&1&0&1&0&0&0&0\\0&0&1&0&0&0&0&0\\1&0&1&0&0&0&0&0\\0&0&0&0&0&0&0&0\\0&0&0&0&0&0&0&0\\0&0&0&0&0&0&0&0\\0&0&0&0&0&0&0&0\end{bmatrix}\)
each of these two query has 8 element, it stored the position where the element in the matrix is not 0, they have similar purpose as
A sparse polynomial \(\widetilde{M}\) can be represented by \(n\) tuples of the form \((i,j,M(i,j))\) is encoded by three vector:
\(row(k)=i, col(k)=j,val(k)=M(i,j)\) where \(k\in [0,n-1]\)