Converse bounds for multiple graph alignment and correlation detection based on last matching
The paper focuses on information theoretic converse bounds for the alignment of $m$ correlated graphs and for the detection of correlation among $m$ graphs. A simple idea for $m\geq 3$ is that if the alignment of $m-1$ of the graphs is revealed as extra information (by a genie for example) then it is still necessary to produce the alignment between the one remaining graph and the others, i.e. the last matching must be accomplished. For both Gaussian and Erdos-Renyi models, the last-matching problem is equivalent to one with two observed graphs, providing a path to extend converse bounds for…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2608.14450
curl -X POST /api/v1/records/arxiv/2608.14450/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2608.14450/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'