Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR26-172 | 8th September 2026 17:30

Design Methodologies for Interactive Proof Systems

RSS-Feed

Abstract:

We present a methodology for constructing interactive proof systems.
This methodology, which is implicit in prior works, consists of reducing the original claim to an iteratively generated sequence of claims such that each claim is (interactively) generated based on the prior claim.
Viewing each of these interactive generation steps as solving an adequate search problem, we present composition results that support a modular construction of interactive proof systems as well as their transformations to PCIPs (aka IOPs).

The development of the foregoing methodology involves the explicit introduction of a few notions, which are of independent interest.
These include ``dichotomous search problems'' (to be solved by protocols analogous to interactive proofs) and oracle-aided protocols (in which the oracle is a search problem rather than a decision problem).

Using the foregoing methodology, we prove that every set in uniform-$\cal NC$ has a doubly-efficient PCIP.
This result was conjectured by Arnon, Chiesa, and Yogev ({\em 37th CCC}, 2022), and our construction follows their ideas.
Our contribution is in adapting their ``IP to PCIP'' transformation to the context of oracle-aided protocols and applying the foregoing methodology while following the ideas of Goldwasser, Kalai, and Rothblum ({\em 40th STOC}, 2008).



ISSN 1433-8092 | Imprint