Paper 2022/168

Hardness of Approximation for Stochastic Problems via Interactive Oracle Proofs

Gal Arnon, Alessandro Chiesa, and Eylon Yogev

Abstract

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 \emph{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 \emph{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 \emph{constant} query complexity (\emph{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.

Metadata
Available format(s)
PDF
Category
Foundations
Publication info
Preprint. MINOR revision.
Keywords
hardness of approximationinteractive oracle proofsstochastic satisfaction problems
Contact author(s)
gal arnon @ weizmann ac il
alessandro chiesa @ epfl ch
eylon yogev @ biu ac il
History
2022-02-20: received
Short URL
https://ia.cr/2022/168
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2022/168,
      author = {Gal Arnon and Alessandro Chiesa and Eylon Yogev},
      title = {Hardness of Approximation for Stochastic Problems via Interactive Oracle Proofs},
      howpublished = {Cryptology ePrint Archive, Paper 2022/168},
      year = {2022},
      note = {\url{https://eprint.iacr.org/2022/168}},
      url = {https://eprint.iacr.org/2022/168}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.