Document Open Access Logo

Twenty-Two New Approximate Proof Labeling Schemes

Authors Yuval Emek, Yuval Gil

PDF
Thumbnail PDF

File

LIPIcs.DISC.2020.20.pdf
  • Filesize: 0.49 MB
  • 14 pages

Document Identifiers

Author Details

Yuval Emek
  • Technion - Israel Institute of Technology, Haifa, Israel
Yuval Gil
  • Technion - Israel Institute of Technology, Haifa, Israel

Funding

This work has been supported by an Israeli Science Foundation grant number 1016/17.

Cite AsGet BibTex

Yuval Emek and Yuval Gil. Twenty-Two New Approximate Proof Labeling Schemes. In 34th International Symposium on Distributed Computing (DISC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 179, pp. 20:1-20:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
https://doi.org/10.4230/LIPIcs.DISC.2020.20

Abstract

Introduced by Korman, Kutten, and Peleg (Distributed Computing 2005), a proof labeling scheme (PLS) is a system dedicated to verifying that a given configuration graph satisfies a certain property. It is composed of a centralized prover, whose role is to generate a proof for yes-instances in the form of an assignment of labels to the nodes, and a distributed verifier, whose role is to verify the validity of the proof by local means and accept it if and only if the property is satisfied. To overcome lower bounds on the label size of PLSs for certain graph properties, Censor-Hillel, Paz, and Perry (SIROCCO 2017) introduced the notion of an approximate proof labeling scheme (APLS) that allows the verifier to accept also some no-instances as long as they are not "too far" from satisfying the property. The goal of the current paper is to advance our understanding of the power and limitations of APLSs. To this end, we formulate the notion of APLSs in terms of distributed graph optimization problems (OptDGPs) and develop two generic methods for the design of APLSs. These methods are then applied to various classic OptDGPs, obtaining twenty-two new APLSs. An appealing characteristic of our APLSs is that they are all sequentially efficient in the sense that both the prover and the verifier are required to run in (sequential) polynomial time. On the negative side, we establish "combinatorial" lower bounds on the label size for some of the aforementioned OptDGPs that demonstrate the optimality of our corresponding APLSs. For other OptDGPs, we establish conditional lower bounds that exploit the sequential efficiency of the verifier alone (under the assumption that NP ≠ co-NP) or that of both the verifier and the prover (under the assumption that P ≠ NP, with and without the unique games conjecture).

Subject Classification

ACM Subject Classification
  • Theory of computation → Distributed algorithms
  • Theory of computation → Approximation algorithms analysis
Keywords
  • proof labeling schemes
  • distributed graph problems
  • approximation algorithms

Metrics

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

Related Versions

References

  1. B. Awerbuch, B. Patt-Shamir, and G. Varghese. Self-stabilization by local checking and correction. In Proceedings 32nd Annual Symposium of Foundations of Computer Science, pages 268-277, 1991. Google Scholar
  2. Nir Bacrach, Keren Censor-Hillel, Michal Dory, Yuval Efron, Dean Leitersdorf, and Ami Paz. Hardness of distributed optimization. In Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing, 2019. Google Scholar
  3. Alkida Balliu, Gianlorenzo D'Angelo, Pierre Fraigniaud, and Dennis Olivetti. What can be verified locally? J. Comput. Syst. Sci., 97:106-120, 2018. Google Scholar
  4. Lélia Blin, Pierre Fraigniaud, and Boaz Patt-Shamir. On proof-labeling schemes versus silent self-stabilizing algorithms. In Stabilization, Safety, and Security of Distributed Systems, pages 18-32, 2014. Google Scholar
  5. Keren Censor-Hillel, Ami Paz, and Mor Perry. Approximate proof-labeling schemes. Theor. Comput. Sci., 811:112-124, 2020. Google Scholar
  6. Miroslav Chlebík and Janka Chlebíková. The steiner tree problem on graphs: Inapproximability results. Theor. Comput. Sci., 406(3):207-214, 2008. Google Scholar
  7. Pierluigi Crescenzi, Pierre Fraigniaud, and Ami Paz. Trade-offs in distributed interactive proofs. In 33rd International Symposium on Distributed Computing, pages 13:1-13:17, 2019. Google Scholar
  8. Irit Dinur and Samuel Safra. On the hardness of approximating minimum vertex cover. Annals of Mathematics, 162(1):439-485, 2005. Google Scholar
  9. Irit Dinur and David Steurer. Analytical approach to parallel repetition. In Symposium on Theory of Computing, STOC, pages 624-633, 2014. Google Scholar
  10. Yuval Emek and Yuval Gil. Twenty-two new approximate proof labeling schemes (full version), 2020. URL: http://arxiv.org/abs/2007.14307.
  11. Laurent Feuilloley. Introduction to local certification, 2019. Google Scholar
  12. Laurent Feuilloley and Pierre Fraigniaud. Survey of distributed decision. Bull. EATCS, 119, 2016. Google Scholar
  13. Laurent Feuilloley and Pierre Fraigniaud. Error-sensitive proof-labeling schemes. In 31st International Symposium on Distributed Computing, DISC 2017, October 16-20, 2017, Vienna, Austria, volume 91 of LIPIcs, pages 16:1-16:15, 2017. Google Scholar
  14. Laurent Feuilloley, Pierre Fraigniaud, Juho Hirvonen, Ami Paz, and Mor Perry. Redundancy in distributed proofs. In 32nd International Symposium on Distributed Computing, DISC, volume 121 of LIPIcs, pages 24:1-24:18, 2018. Google Scholar
  15. Pierre Fraigniaud, Amos Korman, and David Peleg. Local distributed decision. In IEEE 52nd Annual Symposium on Foundations of Computer Science, FOCS, pages 708-717, 2011. Google Scholar
  16. Pierre Fraigniaud, Pedro Montealegre, Rotem Oshman, Ivan Rapaport, and Ioan Todinca. On distributed merlin-arthur decision protocols. In Structural Information and Communication Complexity, pages 230-245, 2019. Google Scholar
  17. Pierre Fraigniaud, Boaz Patt-Shamir, and Mor Perry. Randomized proof-labeling schemes. Distributed Comput., 32(3):217-234, 2019. Google Scholar
  18. Mika Göös and Jukka Suomela. Locally checkable proofs in distributed computing. THEORY OF COMPUTING, 12:1–33, 2016. Google Scholar
  19. Johan Håstad. Some optimal inapproximability results. J. ACM, 48(4):798–859, July 2001. Google Scholar
  20. Marek Karpinski, Michael Lampis, and Richard Schmied. New inapproximability bounds for TSP. J. Comput. Syst. Sci., 81(8):1665-1677, 2015. Google Scholar
  21. Subhash Khot. On the power of unique 2-prover 1-round games. In Proceedings of the Thiry-Fourth Annual ACM Symposium on Theory of Computing, page 767–775, 2002. Google Scholar
  22. Subhash Khot, Guy Kindler, Elchanan Mossel, and Ryan O’Donnell. Optimal inapproximability results for max‐cut and other 2‐variable csps? SIAM Journal on Computing, 37(1):319-357, 2007. Google Scholar
  23. Subhash Khot and Oded Regev. Vertex cover might be hard to approximate to within 2-epsilon. J. Comput. Syst. Sci., 74(3):335-349, 2008. Google Scholar
  24. Gillat Kol, Rotem Oshman, and Raghuvansh R. Saxena. Interactive distributed proofs. In PODC 2018 - Proceedings of the 2018 ACM Symposium on Principles of Distributed Computing, pages 255-264, July 2018. Google Scholar
  25. Amos Korman and Shay Kutten. Distributed verification of minimum spanning trees. Distributed Comput., 20(4):253-266, 2007. Google Scholar
  26. Amos Korman, Shay Kutten, and David Peleg. Proof labeling schemes. Distributed Comput., 22(4):215-233, 2010. Google Scholar
  27. E. Kushilevitz and N. Nisan. Communication Complexity. Cambridge University Press, 2006. Google Scholar
  28. Moni Naor, Merav Parter, and Eylon Yogev. The power of distributed verifiers in interactive proofs. In Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms, SODA, pages 1096-115, 2020. Google Scholar
  29. Rafail Ostrovsky, Mor Perry, and Will Rosenbaum. Space-time tradeoffs for distributed verification. In Shantanu Das and Sebastien Tixeuil, editors, Structural Information and Communication Complexity, pages 53-70, Cham, 2017. Springer International Publishing. Google Scholar
  30. Boaz Patt-Shamir and Mor Perry. Proof-labeling schemes: Broadcast, unicast and in between. In Stabilization, Safety, and Security of Distributed Systems - 19th International Symposium, SSS, volume 10616, pages 1-17. Springer, 2017. 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 Imprint Privacy Contact