SNARGs for NP and Non-signaling PCPs, Revisited

Lalita Devadas; Samuel B. Hopkins; Yael Tauman Kalai; Pravesh K. Kothari; Alex Lombardi; Surya Mathialagan

doi:10.1145/3798129.3800782

STOC2026顶会

SNARGs for NP and Non-signaling PCPs, Revisited

Lalita Devadas, Samuel B. Hopkins, Yael Tauman Kalai, Pravesh K. Kothari, Alex Lombardi, Surya Mathialagan

DOI 出版方

2026年份

2被引次数

摘要

We revisit the question of whether it is possible to build succinct non-interactive arguments (SNARGs) for all of NP under standard assumptions using non-signaling probabilistically checkable proofs [Kalai-Raz-Rothblum, STOC’ 14]. In particular, we observe that using exponential-length PCPs appears to circumvent all of the existing barriers.

问问这篇 Paper

问问你的智能体。

Lune 读过与它相关的顶会 Paper，每个回答都会注明依据哪几篇。

核心论断
横向对比
局限

你的问题

智能体调用

Lunesearch_papers

在 Lune 里问

免费开始，无需绑卡

摘要

问问这篇 Paper

问问你的智能体。

相关 Paper