דלג לתוכן (מקש קיצור 's')
אירועים

אירועים והרצאות בפקולטה למדעי המחשב ע"ש הנרי ומרילין טאוב

event speaker icon
יבגניה פרגמנט (הרצאה סמינריונית למגיסטר)
event date icon
יום רביעי, 04.05.2016, 13:30
event location icon
Taub 601
event speaker icon
מנחה: Prof. Eli Ben-Sasson
Due to the lack of computational power, many users don't perform the computation locally, rather outsource the computation to a remote server. This raises the problem of computational integrity. Using Probabilistically Checkable Proofs (PCP) the remote server can prove to the user (with high probability) that the computation was executed correctly. Although every language in NEXP is known to have a PCP system, previous works have not specified the process of converting instances of the bounded halting problem for random access machines (RAM) to instances of a "PCP friendly" NEXP complete language. This problem is highly relevant to the task of creating PCPs for practical problems. We define and describe a general method for representing bounded time RAM programs as instances of a NEXP complete "algebraic constraint satisfaction problem", that are PCP friendly.