Timeline for GKR Protocol - is it one Sum-Check per layer or is it one Sum-Check per gate?
Current License: CC BY-SA 4.0
8 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Mar 2 at 0:11 | history | bounty ended | user93353 | ||
| Mar 2 at 0:11 | vote | accept | user93353 | ||
| Mar 1 at 19:57 | comment | added | Hilder Vitor Lima Pereira | Btw, consider this: sum-check protocol has verification cost > log|C| . If it was applied to every gate, GKR's verification cost would be |C| log |C|, which is heavier than running the circuit locally, so, it would be pointless. | |
| Mar 1 at 19:56 | comment | added | Hilder Vitor Lima Pereira | @user93353 As I said, I didn't have time to check the video, so I don't know what she is talking about. When I heard "2-to-1 trick" I thought it was the technique to collapse the verification of $W(r')$ and $W(r'')$ into a single verification (and maybe it is). But anyway I've answered your question. If there is something you don't understand in my answer, I will be glad to clarify it. | |
| Mar 1 at 14:44 | comment | added | Hilder Vitor Lima Pereira | Your question was about executing the sum-check protocol one or multiple times per layer. As I said in the answer, you just need one. It seems that she is talking about how you go from layer i to layer i+1 in the recursive step of GKR. If so, this is covered in Thaler's book and, basically, for the next layer you again just need the sum-check protocol one time because of the 2-to-1 trick. But she might also be talking about something else or about a specific application of the GKR protocol. I didn't have time to watch the full video. | |
| Mar 1 at 1:50 | history | edited | Hilder Vitor Lima Pereira | CC BY-SA 4.0 |
the extension is not multilinear, as it is a product of multilinear extensions
|
| Feb 29 at 12:28 | vote | accept | user93353 | ||
| Mar 1 at 9:37 | |||||
| Feb 29 at 11:43 | history | answered | Hilder Vitor Lima Pereira | CC BY-SA 4.0 |