Document Open Access Logo

Hardness of Approximation for Stochastic Problems via Interactive Oracle Proofs

Authors Gal Arnon, Alessandro Chiesa, Eylon Yogev

PDF
Thumbnail PDF

File

LIPIcs.CCC.2022.24.pdf
  • Filesize: 0.7 MB
  • 16 pages

Document Identifiers

Author Details

Gal Arnon
  • Weizmann Institute of Science, Rehovot, Israel
Alessandro Chiesa
  • EPFL, Lausanne, Switzerland
Eylon Yogev
  • Bar-Ilan University, Ramat-Gan, Israel

Funding

  • Arnon, Gal: Supported in part by a grant from the Israel Science Foundation (no. 2686/20) and by the Simons Foundation Collaboration on the Theory of Algorithmic Fairness.
  • Chiesa, Alessandro: Funded by the Ethereum Foundation.
  • Yogev, Eylon: Supported by the BIU Center for Research in Applied Cryptography and Cyber Security in conjunction with the Israel National Cyber Bureau in the Prime Minister’s Office, and by the Alter Family Foundation.

Cite As Get BibTex

Gal Arnon, Alessandro Chiesa, and Eylon Yogev. Hardness of Approximation for Stochastic Problems via Interactive Oracle Proofs. In 37th Computational Complexity Conference (CCC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 234, pp. 24:1-24:16, Schloss Dagstuhl – Leibniz-Zentrum fΓΌr Informatik (2022) https://doi.org/10.4230/LIPIcs.CCC.2022.24

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 stochastic constraint satisfaction problems (SCSPs). An SCSP with 𝗄 alternations is a list of constraints over variables grouped into 2𝗄 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 𝗄 ≀ O(log n), we prove that it is AM[𝗄]-hard to approximate, to within a constant, the value of SCSPs with 𝗄 alternations and constant arity. Before, this was known only for 𝗄 = O(1).
Furthermore, we introduce a natural class of 𝗄-round interactive proofs, denoted IR[𝗄] (for interactive reducibility), and show that several protocols (e.g., the sumcheck protocol) are in IR[𝗄]. Using this notion, we extend our inapproximability to all values of 𝗄: we show that for every 𝗄, approximating an SCSP instance with O(𝗄) alternations and constant arity is IR[𝗄]-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[𝗄 ≀ O(log n)] or in IR[𝗄] has an O(𝗄)-round IOP whose verifier has constant query complexity (regardless of the number of rounds 𝗄). In particular, we derive a "sumcheck protocol" whose verifier reads O(1) bits from the entire interaction transcript.

Subject Classification

ACM Subject Classification
  • Theory of computation β†’ Computational complexity and cryptography
  • Theory of computation β†’ Interactive proof systems
Keywords
  • hardness of approximation
  • interactive oracle proofs
  • stochastic satisfaction problems

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

References

  1. Amir Abboud and Arturs Backurs. Towards hardness of approximation for polynomial time problems. In Proceedings of the 8th Innovations in Theoretical Computer Science Conference, ITCS '17, pages 11:1-11:26, 2017. Google Scholar
  2. Amir Abboud and Aviad Rubinstein. Fast and deterministic constant factor approximation algorithms for LCS imply new circuit lower bounds. In Proceedings of the 9th Innovations in Theoretical Computer Science Conference, ITCS '18, pages 35:1-35:14, 2018. Google Scholar
  3. Amir Abboud, Aviad Rubinstein, and R. Ryan Williams. Distributed PCP theorems for hardness of approximation in P. In Proceedings of the 59th Annual IEEE Symposium on Foundations of Computer Science, FOCS '17, pages 25-36, 2017. Google Scholar
  4. Gal Arnon, Alessandro Chiesa, and Eylon Yogev. A PCP theorem for interactive proofs. Cryptology ePrint Archive, Report 2021/915, 2022. To appear at EUROCRYPT 2022. Google Scholar
  5. Sanjeev Arora, Carsten Lund, Rajeev Motwani, Madhu Sudan, and Mario Szegedy. Proof verification and the hardness of approximation problems. Journal of the ACM, 45(3):501-555, 1998. Preliminary version in FOCS '92. Google Scholar
  6. Sanjeev Arora and Shmuel Safra. Probabilistic checking of proofs: a new characterization of NP. Journal of the ACM, 45(1):70-122, 1998. Preliminary version in FOCS '92. Google Scholar
  7. Eli Ben-Sasson, Alessandro Chiesa, and Nicholas Spooner. Interactive oracle proofs. In Proceedings of the 14th Theory of Cryptography Conference, TCC '16-B, pages 31-60, 2016. Google Scholar
  8. Lijie Chen, Shafi Goldwasser, Kaifeng Lyu, Guy N. Rothblum, and Aviad Rubinstein. Fine-grained complexity meets IP = PSPACE. In Proceedings of the 30th Annual Symposium on Discrete Algorithms, SODA '19, pages 1-20, 2019. Google Scholar
  9. Lijie Chen and Ryan Williams. An equivalence class for orthogonal vectors. In Proceedings of the 30th Annual Symposium on Discrete Algorithms, SODA '19, pages 21-40, 2019. Google Scholar
  10. Anne Condon, Joan Feigenbaum, Carsten Lund, and Peter W. Shor. Random debaters and the hardness of approximating stochastic functions. SIAM Journal on Computing, 26(2):369-400, 1997. Google Scholar
  11. Irit Dinur. The PCP theorem by gap amplification. Journal of the ACM, 54(3):12, 2007. Google Scholar
  12. Andrew Drucker. A PCP characterization of AM. In Proceedings of the 38th International Colloquium on Automata, Languages and Programming, ICALP '11, pages 581-592, 2011. Google Scholar
  13. Uriel Feige, Shafi Goldwasser, Laszlo LovΓ‘sz, Shmuel Safra, and Mario Szegedy. Interactive proofs and the hardness of approximating cliques. Journal of the ACM, 43(2):268-292, 1996. Google Scholar
  14. Oded Goldreich, Salil Vadhan, and Avi Wigderson. On interactive proofs with a laconic prover. Computational Complexity, 11(1/2):1-53, 2002. Google Scholar
  15. Shafi Goldwasser, Yael Tauman Kalai, and Guy N. Rothblum. Delegating computation: Interactive proofs for muggles. Journal of the ACM, 62(4):27:1-27:64, 2015. Google Scholar
  16. Ishay Haviv, Oded Regev, and Amnon Ta-Shma. On the hardness of satisfiability with bounded occurrences in the polynomial-time hierarchy. Theory of Computing, 3(1):45-60, 2007. Google Scholar
  17. Ker-I Ko and Chih-Long Lin. Non-approximability in the polynomial-time hierarchy. Technical Report 94-2, Dept. of Computer Science, SUNY at Stony Brook, 1994. Google Scholar
  18. Carsten Lund, Lance Fortnow, Howard J. Karloff, and Noam Nisan. Algebraic methods for interactive proof systems. Journal of the ACM, 39(4):859-868, 1992. Google Scholar
  19. Christos H. Papadimitriou. Games against nature (extended abstract). In Proceedings of the 24th Annual ACM Symposium on Theory of Computing, STOC '83, pages 446-450, 1983. Google Scholar
  20. Omer Reingold, Ron Rothblum, and Guy Rothblum. Constant-round interactive proofs for delegating computation. In Proceedings of the 48th ACM Symposium on the Theory of Computing, STOC '16, pages 49-62, 2016. Google Scholar
  21. Adi Shamir. IP = PSPACE. Journal of the ACM, 39(4):869-877, 1992. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact