Ron Rothblum: How to Delegate Computations: The Power of No-Signaling Proofs
465 views · Published 7 May 2014 · 42:46 · Indexed 14 November 2026
Channel: Hebrew University of Jerusalem · 2014 · Education
Ron Rothblum (Weizmann Inst.) How to Delegate Computations: The Power of No-Signaling Proofs We construct a 1-round delegation scheme (i.e., argument-system) for every language computable in time t=t(n), where the running time of the prover is poly(t) and the running time of the verifier is n*polylog(t). In particular, for every language in P we obtain a delegation scheme with almost linear time verification. Our construction relies on the existence of a computational sub-exponentially secure private information retrieval scheme.
More from this channel
-
1:22:14
פרופ' אברהם הוכברג- הגן H-19, תקווה חדשה לחולי סרטן
-
1:22:54
מר משה נגבי- על היעדר האחריותיות בדמוקרטיה הישראלית
-
1:30:58
פרופ' ששון צחייק- מדע הכימיה
-
1:13:59
פרופ' אבנר דה שליט- על מורשת, מקום ותכנון בר קיימא
-
1:17:03
פרופ' ארי לאור- עדויות לקיומם של חורים שחורים ענקיים
-
1:07:28
פרופ' ניר שביב- על קרינה קוסמית ואקלים כדור-הארץ
-
1:21:11
ד"ר דני צ'רנוב- השפעת שינויי האקלים על שונית האלמוגים
-
1:06:27
ד"ר ארז ריבק - חידוד הדמות בשמים ובעיניים