Citeam recent ziarul O abordare non-PCP a cunoștințelor zero cuantice succinte.
Printre altele, se discută o adaptare a tehnicii de „pliere” (de la Bulletproofs) la dovezile bazate pe SIS.
Hârtia măsoară distanțele în $\ell_\infty$ normă (mai degrabă decât $\ell_2$), și este vag cu privire la alegerea de încorporare pe care o folosește (deși îmi imaginez că este încorporarea coeficientului).
Aceste alegeri înseamnă că preia factori suplimentari de $n$ la delimitarea normei înmulţirilor în special.
De exemplu, la un moment dat (la pagina 20) ei doresc să stabilească o limită
$$\lVert 8\lambda_i\rVert_\infty \leq 2n^2$$
Unde $\lambda_i$ este de forma
$$\lambda_i = \pm\frac{f}{(X^u-X^v)(X^v-X^w)(X^w-X^u)},$$
$\lVert f\rVert_1 \leq 2$, și se știe că $2/(X^i-X^j)$ are coeficienți în $\{-1,0,1\}$ pentru $i\neq j$.
Pot stabili limita dorită după cum urmează
Scrie $$8\lambda_i = \pm f \frac{2}{X^u-X^v}\frac{2}{X^v-X^w}\frac{2}{X^w-X^u}$$
Pentru fiecare înmulțire, utilizați un rezultat de forma care $\lVert rs\rVert_\infty \leq \lVert r\rVert_\infty\lVert s\rVert_\infty \min(\lVert r\rVert_0,\lVert s\rVert_0)$. În special, pentru produse-și $r, s$ non-rare, avem asta $\min(\lVert r\rVert_0,\lVert s\rVert_0) \leq n$, pierzându-ne un factor de $n$ pe fiecare dintre înmulțiri (nu implică $f$), și un factor de 2 la înmulțirea care implică $f$.
Inegalitatea $\lVert rs\rVert_\infty \leq \lVert r\rVert_\infty \lVert s\rVert_\infty \min(\lVert r\rVert_0,\lVert s\rVert_0)$ (sau ceva foarte apropiat de acesta --- poate lipsește un factor constant de 2) ar trebui să fie valabil pentru fiecare coeficient din produs $rs$ este convoluția coeficienților lui $r$ și $s$.
Această circumvoluție are $\min(\lVert r\rVert_0, \lVert s\rVert_0)$ mulți termeni non-zero și fiecare dintre aceste sume non-zero are dimensiunea cel mult $\lVert r\rVert_\infty \lVert s\rVert_\infty$.
În special, aceasta înseamnă că atunci când se analizează $\lVert rs\rVert_\infty$, adesea (implicit) au legat acest lucru ca $\lVert rs\rVert_\infty \leq n\lVert r\rVert_\infty\lVert s\rVert_\infty$, preluând un factor suplimentar de $n$ pentru fiecare înmulțire (cu excepția înmulțirii cu $f$, care este rar).
Acest lucru trebuie să fie contrastat cu analiza din încorporarea canonică (și $\ell_2$-normă), unde sub-multiplicativitatea ar obține una care
$$\lVert 8\lambda_i\rVert_2^{can} \leq \lVert f\rVert_2^{can}(\lVert 2/(X^i-X^j)\rVert_2^{can})^3$$
preluând niciun factor suplimentar de $n$ pe parcurs (deși cred $\lVert r\rVert_2^{can} = \sqrt{n}\lVert r\rVert_2$, deci pot exista unii factori impliciti ai $n$ ridicat).
Presupun că întrebarea mea generală este
Există vreun motiv conceptual pentru care încorporarea canonică pare mai puțin populară în lucrările pe sistemele de demonstrare bazate pe zăbrele?
Aveam impresia că atunci când se dorește optimizarea limitelor (în special a limitelor care implică înmulțiri!), înglobarea canonică este în general de preferat datorită sub-multiplicativității.
Dar în lectura mea superficială, încorporarea coeficientului pare mai populară în lucrările pe sisteme de dovezi și sunt interesat să știu de ce.
