Search Results

Documents authored by Shamir, Dana


Document
Explicit Space-Time Tradeoffs for Proof Labeling Schemes in Graphs with Small Separators

Authors: Orr Fischer, Rotem Oshman, and Dana Shamir

Published in: LIPIcs, Volume 217, 25th International Conference on Principles of Distributed Systems (OPODIS 2021)


Abstract
In distributed verification, our goal is to verify that the network configuration satisfies some desired property, using pre-computed information stored at each network node. This is formally modeled as a proof labeling scheme (PLS): a prover assigns to each node a certificate, and then the nodes exchange their certificates with their neighbors and decide whether to accept or reject the configuration. Subsequent work has shown that in some specific cases, allowing more rounds of communication - so that nodes can communicate further across the network - can yield shorter certificates, trading off the space required to store the certificate against the time required for verification. Such tradeoffs were previously known for trees, cycles, and grids, or for proof labeling schemes where all nodes receive the same certificate. In this work we show that in large classes of graphs, every one-round PLS can be transformed into a multi-round PLS with shorter certificates. We give two constructions: given a 1-round PLS with certificates of 𝓁 bits, in graphs families with balanced edge separators of size s(n), we construct a t-round PLS with certificates of size Õ(𝓁 ⋅ s(n) / t), and in graph families with an excluded minor and maximum degree Δ, we construct a t-round PLS with certificates of size Õ(𝓁 ⋅ Δ / √t). Our constructions are explicit, and we use erasure codes to exploit the larger neighborhood viewed by each node in a t-round PLS.

Cite as

Orr Fischer, Rotem Oshman, and Dana Shamir. Explicit Space-Time Tradeoffs for Proof Labeling Schemes in Graphs with Small Separators. In 25th International Conference on Principles of Distributed Systems (OPODIS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 217, pp. 21:1-21:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)


Copy BibTex To Clipboard

@InProceedings{fischer_et_al:LIPIcs.OPODIS.2021.21,
  author =	{Fischer, Orr and Oshman, Rotem and Shamir, Dana},
  title =	{{Explicit Space-Time Tradeoffs for Proof Labeling Schemes in Graphs with Small Separators}},
  booktitle =	{25th International Conference on Principles of Distributed Systems (OPODIS 2021)},
  pages =	{21:1--21:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-219-8},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{217},
  editor =	{Bramas, Quentin and Gramoli, Vincent and Milani, Alessia},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2021.21},
  URN =		{urn:nbn:de:0030-drops-157969},
  doi =		{10.4230/LIPIcs.OPODIS.2021.21},
  annote =	{Keywords: proof-labeling schemes, space-time tradeoffs, families with excluded minor}
}
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