Probabilistic Checking against Non-Signaling Strategies

云计算是一种范式，它提供对计算资源的访问，例如存储数据或执行超出用户计算能力的复杂计算。在云计算中，委托计算的问题涉及这样的设置：计算能力较弱的设备，即客户端（或验证者），希望将计算任务外包给强大但不受信任的一方，即服务器（或证明者）。由于服务器在执行计算时可能会出错，因此除了答案之外，还需要提供计算正确完成的证明。当然，我们要求验证这个证明比计算本身要“容易”得多。也就是说，客户机的运行时间应该小于在没有任何额外帮助的情况下执行计算所需的时间。******最近，在构建这种委托方案的目标的激励下，引入了多证明者交互证明系统（mip）的概念，该概念可以有效地对抗非信令对手（nsmip）。量子物理文献中已经研究了非信号策略，它是量子纠缠策略的严格推广，在最小要求下考虑所有可能的关联，尊重物理学中的“无瞬时通信”原则。******虽然近年来在构建nsmip方面取得了一些进展，但我们对这种证明系统的理解仍然有限。事实上，对于经典证明系统，我们有丰富的工具和技术库，而对于非经典证明系统，许多基本问题仍然是开放的，目前的技术相对有限。例如，PCP定理（在经典设置中）表明，对于NEXP中的任何语言，在多项式时间验证者和两个非通信证明者之间都有一个1轮协议，其中验证者向证明者发送随机查询，每个证明者都用短消息响应，允许验证者以高概率决定给定输入是否属于该语言。相比之下，PCP定理的（适当陈述的）非信号模拟是未知的。对于EXP中的任何语言，非信号设置中最著名的结果都需要多项式数量的证明器，但三个证明器也可能足够了。******这个项目将有助于系统地研究证明系统的力量和局限性，这些证明系统对非信号策略是健全的。我们将研究与非信令策略相关的基本问题，包括研究非信令设置中的属性测试（如低度测试），并应用这些技术获得具有最优参数的nsmip。******这项研究将显示物理学和计算科学（最著名的是复杂性理论和密码学）之间的紧密联系，并将加强他们的科学社区之间的联系。*****

Cloud computing is a paradigm that provides access to computational resources, such as storing data or performing complex computation, that are beyond the computational power of the user. In cloud computing the problem of delegating computation is concerned with the setting where a computationally weak device, the client (or the verifier), wishes to outsource a computational task to a powerful but untrusted party, the server (or the prover). Since the server can, potentially, err when performing the computation, it is required in addition to the answer to also provide a proof that the computation was done correctly. Naturally, we require that verifying this proof is significantly `easier' than doing the computation itself. That is, the running time of the client should be smaller than the time required to perform the computation without any additional help.******Recently, motivated by the goal of constructing such delegation schemes, the notion of multi--prover interactive proof systems (MIPs) that are sound against non--signaling adversaries (nsMIPs) has been introduced. Non--signaling strategies have been studied in the quantum physics literature, and are strict generalization of quantum entangled strategies that consider all possible correlations under the minimal requirement that respects the ''no instantaneous communication'' principle in physics.******Although in the recent years there has been some progress in constructing nsMIPs, our understanding of such proof systems remains limited. Indeed, while for classical proof systems we have a rich arsenal of tools and techniques, for non--classical proof systems many fundamental questions are still open, and the current techniques are relatively restricted. For example, the PCP Theorem (in the classical setting) says that for any language in NEXP there is a 1-round protocol between a polynomial time verifier and two non--communicating provers, where the verifier send random queries to the provers, each of the provers responds with a short message, allowing the verifier to decide with high probability whether a given input belongs to the language or not. In contrast, the (appropriately stated) non--signaling analogue of the PCP theorem is not known. The best known results in the non--signaling setting require a polynomial number of provers for any languages in EXP, but it may well be that three provers suffice as well.******This project will contribute to the systematic study of the power and limitations of proof systems that are sound against non--signaling strategies. We will investigate fundamental problems related to non-signaling strategies, including studying property testing in the non-signaling setting (such as low-degree testing), and apply theses techniques to obtain nsMIPs with optimal parameters.******The research will show strong ties between Physics and Computing Science (most notably Complexity Theory and Cryptography), and will strengthen the connections between their scientific communities.*****