Skip to content (access key 's')
Logo of Technion
Logo of CS Department

The Taub Faculty of Computer Science Events and Talks

Algebraic RAM
event speaker icon
Evgenya Pergament (M.Sc. Thesis Seminar)
event date icon
Wednesday, 04.05.2016, 13:30
event location icon
Taub 601
event speaker icon
Advisor: 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.