- Rating
- 2
- Confidence
- 2
- Informativeness
- 2
- Presentation
- 3
- Soundness
- 3
Read review
Paper summary
The paper studies private coordination of bounded reciprocal neighbor shortlists. A pure edge-private public transcript defines a candidate graph; each vertex intersects its private adjacency list with that graph. The sequential protocol establishes near-capacity saturation and, for capacity of order log(n/rho)/(eta epsilon), simultaneously approximates the optimum same-capacity edge count and preserves an ordinary matching within a factor 2+eta. It uses O(n) rounds, with an O(n log n)-bit encoding of the completed unit-step transcript. Lower bounds distinguish explicit candidates, almost-sure degree caps, and probabilistic local decoding. A representation theorem characterizes deterministic, valid, endpoint-consistent local decoders under the stated pure-privacy assumptions. Parallel and insertion-only streaming variants are also presented. Validation is theoretical.
Critical strengths
-
Theorem 3 gives both same-capacity approximation and matching preservation on one success event. Proposition 7 and Theorem 8 explain the importance of probabilistic feasibility and establish a capacity obstruction in the main fixed-accuracy regime. This is more informative than an isolated approximation algorithm.
-
Theorem 9 shows that intersection decoding captures a broader class of deterministic consistent local rules, subject to its explicit input and state restrictions. It helps distinguish a convenient construction from a property forced by the chosen privacy and consistency requirements.
Critical weaknesses
-
Appendix G.4 treats reciprocal standby-directory planning as the completed task, which is a legitimate boundary. However, each site already stores its entire eligibility row. Merely marking a bounded subset does not save storage of the underlying relationships. The paper needs to identify what scarce resource b actually limits and what decision the shortlist enables. Reservations, maintenance, or downstream computation could supply such a role, but the current workflow does not make one concrete. It also does not sufficiently connect same-capacity edge count and matching containment to success in that decision. This matters because the b >= n−1 case is trivial with zero privacy loss: the value of private truncation depends on a reason to require smaller directories.
-
A private protocol need not solve activation or release a final matching to be valuable, and I do not require deployment or new experiments from a theory paper. Nevertheless, the paper should explain why this decoder class is the right abstraction for a named class of consequential coordination tasks, or why its explicit/implicit and zero-failure separations settle an important question independently of the application. The unresolved eta dependence and the distinction between quadratic online messages and compact stored history further limit conclusions about the useful operating regime. These are scope and significance concerns, not counterexamples to the theorems.
Questions for authors
- In the standby-directory application, what resource does the capacity b constrain, and why does marking a subset of an already-stored eligibility row relieve an actual bottleneck?
- What concrete decision uses the shortlist, and how do the two approximation guarantees translate into a success criterion for it? Which relationship disclosures are permitted at activation, and why is the planning-stage protection boundary appropriate for that need?
- Can the paper articulate the significance of the representation and separation results independently of this application, with the relevant decoder restrictions kept explicit?
Summary of revisions to the paper
We thank the reviewers for their time, questions, and helpful comments. Below, we summarize the changes we made to our revision of the paper (uploaded as the newest revision in this submission). The reviewer requesting the corresponding change is given in parentheses, eg. (Reviewer X).