DELEGATING COMPUTATION VIA NO-SIGNALING STRATEGIES
Yael Tauman Kalai
Efficient verification of computation, also known as delegation of computation , is one of the most fundamental notions in computer science, and in particular it lies at the heart of the P vs. NP question. This article contains a high level overview of the evolution of proofs in computer science, and shows how this evolution is instrumental to solving the problem of delegating computation. We highlight a curious connection between the problem of delegating computation and the notion of no-signaling strategies from quantum physics.
International Congress of Mathematicians (ICM)•May 1, 2019•0 citations