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\\1&1&0&1\\0&0&1&0\\1&0&1&0\end{bmatrix}\)
The matrix has 16 elements but only 8 elements are not 0
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]\)
so in this case it is:
\(k=0: (0,0,M(0,0))\) ,\(k=1: (0,2,M(0,2))\) ,
\(k=2:(1,0,M(1,0))\) ,\(k=3:(1,1,M(1,1))\)
\(k=4:(1,3,M(1,3))\) ,\(k=5:(2,2,M(2,2))\) ,
\(k=6:(3,0,M(3,0))\) ,\(k=7:(3,2,M(3,2))\)
now it is clear \(i,j\) are both two bits
let’s clarify the parameters til now:
m= 4, s=2, n=8,u=4