{"id":8775,"date":"2025-12-02T07:02:31","date_gmt":"2025-12-02T07:02:31","guid":{"rendered":"https:\/\/mailitics.com\/index.php\/2025\/12\/02\/2512-00610\/"},"modified":"2025-12-02T07:02:31","modified_gmt":"2025-12-02T07:02:31","slug":"2512-00610","status":"publish","type":"post","link":"https:\/\/mailitics.com\/index.php\/2025\/12\/02\/2512-00610\/","title":{"rendered":"Statistical-computational gap in multiple Gaussian graph alignment"},"content":{"rendered":"

Statistical-computational gap in multiple Gaussian graph alignment
\n \t

\n
<\/BR>
\n
\n \t

\n
<\/BR><\/p>\n

arXiv:2512.00610v1 Announce Type: new
\nAbstract: We investigate the existence of a statistical-computational gap in multiple Gaussian graph alignment. We first generalize a previously established informational threshold from Vassaux and Massouli’e (2025) to regimes where the number of observed graphs $p$ may also grow with the number of nodes $n$: when $p leq O(n\/log(n))$, we recover the results from Vassaux and Massouli’e (2025), and $p geq Omega(n\/log(n))$ corresponds to a regime where the problem is as difficult as aligning one single graph with some unknown “signal” graph. Moreover, when $log p = omega(log n)$, the informational thresholds for partial and exact recovery no longer coincide, in contrast to the all-or-nothing phenomenon observed when $log p=O(log n)$. Then, we provide the first computational barrier in the low-degree framework for (multiple) Gaussian graph alignment. We prove that when the correlation $rho$ is less than $1$, up to logarithmic terms, low degree non-trivial estimation fails. Our results suggest that the task of aligning $p$ graphs in polynomial time is as hard as the problem of aligning two graphs in polynomial time, up to logarithmic factors. These results characterize the existence of a statistical-computational gap and provide another example in which polynomial-time algorithms cannot handle complex combinatorial bi-dimensional structures.<\/div>\n

\t

\n
<\/BR>
\n Bertrand Even, Luca Ganassali
\n \t

\n
<\/BR>
\nGo to original source<\/a>
\n \t

\n
<\/BR><\/p>\n","protected":false},"excerpt":{"rendered":"

Statistical-computational gap in multiple Gaussian graph alignment arXiv:2512.00610v1 Announce Type: new Abstract: We investigate the existence of a statistical-computational gap in multiple Gaussian graph alignment. We first generalize a previously established informational threshold from Vassaux and Massouli’e (2025) to regimes where the number of observed graphs $p$ may also grow with the number of nodes […]<\/p>\n","protected":false},"author":2,"featured_media":0,"comment_status":"closed","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[62,113,190,112,191],"tags":[4339,339,1148],"class_list":["post-8775","post","type-post","status-publish","format-standard","hentry","category-aimldsaimlds","category-cs-lg","category-math-st","category-stat-ml","category-stat-th","tag-computational","tag-graph","tag-log"],"_links":{"self":[{"href":"https:\/\/mailitics.com\/index.php\/wp-json\/wp\/v2\/posts\/8775"}],"collection":[{"href":"https:\/\/mailitics.com\/index.php\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/mailitics.com\/index.php\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/mailitics.com\/index.php\/wp-json\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"https:\/\/mailitics.com\/index.php\/wp-json\/wp\/v2\/comments?post=8775"}],"version-history":[{"count":0,"href":"https:\/\/mailitics.com\/index.php\/wp-json\/wp\/v2\/posts\/8775\/revisions"}],"wp:attachment":[{"href":"https:\/\/mailitics.com\/index.php\/wp-json\/wp\/v2\/media?parent=8775"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/mailitics.com\/index.php\/wp-json\/wp\/v2\/categories?post=8775"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/mailitics.com\/index.php\/wp-json\/wp\/v2\/tags?post=8775"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}