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

STOC2026Top-tier venue

SNARGs for NP and Non-signaling PCPs, Revisited

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

DOI Publisher

2026Year

2Citations

Abstract

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.

Ask about this paper

Ask your agent about it.

Lune has read the top-tier papers around this one, so every answer names the papers it rests on.

What it claims
How it compares
Where it falls short

You ask

Your agent calls

Lunesearch_papers

Ask in Lune

Free to start. No credit card required.

Abstract

Ask about this paper

Ask your agent about it.

Related papers