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.