Evgenya Pergament, M.Sc. Thesis Seminar
Wednesday, 4.5.2016, 13:30
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
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.