My own interest in this work is due to the surprising/interesting PCIP (aka IOP) scheme that it constructs.
Recall that in a PCIP scheme the prover's messages are not read in full by the verifier, who merely probes (few) bits in them. It comes to reason that, in typical cases, the verifier probes (few) bits in each of the messages, and this is indeed the case in all prior constructions.
Interestingly, the current work shows how to transform, for any $k$ that is at most logarithmic in the input length, any public-key $k$-round interactive proof into an $O(k)$-round PCIP that makes a constant number of queries.
The resulting PCIP runs $2k choose k$ copies of the original concurrently but not in parallel such that all copies use the same verifier coins and each copy is active only in $k$ of the rounds. Specifically, each copy corresponds to a $k$-subset $S$ of $[2k]$ and is active in the rounds that correspond to $S$, using the coins sent by the verifier in that round. That is, in round $i in S$, when receiving coins $r_i$, the prover in the copy associated with $S$ responds as the original prover would have responded in round $|{j in S: j leq i}|$ on coins $r_i$. In addition, in each round and in each copy, the resulting prover resends the message sent in the prior round (equiv., the prior partial transcript). After these $2r$ rounds of interaction, the prover (re)sends the transcripts of all $2k choose k$ interactions, and the verifier checks the validity of all transcripts (via an auxiliary PCP) as well as the consistency of these transcripts with the messages sent in a randomly selected round.
Hardness of approximation aims to establish lower bounds on the approximability of optimization problems in NP and beyond. We continue the study of hardness of approximation for problems beyond NP, specifically for stochastic constraint satisfaction problems (SCSPs). An SCSP with k alternations is a list of constraints over variables grouped into 2k blocks, where each constraint has constant arity. An assignment to the SCSP is defined by two players who alternate in setting values to a designated block of variables, with one player choosing their assignments uniformly at random and the other player trying to maximize the number of satisfied constraints.
In this paper, we establish hardness of approximation for SCSPs based on interactive proofs. For k leq O(log n), we prove that it is AM[k]-hard to approximate, to within a constant, the value of SCSPs with k alternations and constant arity. Before, this was known only for k = O(1).
Furthermore, we introduce a natural class of k-round interactive proofs, denoted IR[k] (for interactive reducibility), and show that several protocols (e.g., the sumcheck protocol) are in IR[k]. Using this notion, we extend our inapproximability to all values of k: we show that for every k, approximating an SCSP instance with O(k) alternations and constant arity is IR[k]-hard.
While hardness of approximation for CSPs is achieved by constructing suitable PCPs, our results for SCSPs are achieved by constructing suitable IOPs (interactive oracle proofs). We show that every language in AM[k leq O(log n)] or in IR[k] has an O(k)-round IOP whose verifier has constant query complexity (regardless of the number of rounds k). In particular, we derive a “sumcheck protocol” whose verifier reads O(1) bits from the entire interaction transcript.
See https://eprint.iacr.org/2022/168.