The Taub Faculty of Computer Science Events and Talks

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.