Proof-labeling schemes: Broadcast, unicast and in between

Boaz Patt-Shamir, Mor Perry

פרסום מחקרי: פרסום בכתב עתמאמרביקורת עמיתים


We study the effect of limiting the number of different messages a node can transmit simultaneously on the verification complexity of proof-labeling schemes (PLS). In a PLS, each node is given a label, and the goal is to verify, by exchanging messages over each link in each direction, that a certain global predicate is satisfied by the system configuration. We consider a single parameter r that bounds the number of distinct messages that can be sent concurrently by any node: in the case r=1, each node may only send the same message to all its neighbors (the broadcast model), in the case r≥Δ, where Δ is the largest node degree in the system, each neighbor may be sent a distinct message (the unicast model), and in general, for 1≤r≤Δ, each of the r messages is destined to a subset of the neighbors. We show that message compression linear in r is possible for verifying fundamental problems such as the agreement between edge endpoints on the edge state. Some problems, including verification of maximal matching, exhibit a large gap in complexity between r=1 and r>1. For some other important predicates, the verification complexity is insensitive to r, e.g., the question whether a subset of edges constitutes a spanning-tree. We also consider the congested clique model. We show that the crossing technique [1] for proving lower bounds on the verification complexity can be applied in the case of congested clique only if r=1. Together with a new upper bound, this allows us to determine the verification complexity of MST in the broadcast clique. Finally, we establish a general connection between the deterministic and randomized verification complexity for any given number r.

שפה מקוריתאנגלית
עמודים (מ-עד)179-195
מספר עמודים17
כתב עתTheoretical Computer Science
מזהי עצם דיגיטלי (DOIs)
סטטוס פרסוםפורסם - 26 יוני 2022

ASJC Scopus subject areas

  • ???subjectarea.asjc.2600.2614???
  • ???subjectarea.asjc.1700.1700???

טביעת אצבע

להלן מוצגים תחומי המחקר של הפרסום 'Proof-labeling schemes: Broadcast, unicast and in between'. יחד הם יוצרים טביעת אצבע ייחודית.

פורמט ציטוט ביבליוגרפי