AI summaryⓘ
The authors study a way to detect special patterns in certain random graphs called noisy random lifts, compared to completely random regular graphs. They focus on mathematical tools called low degree polynomial threshold functions to analyze this detection problem. Along the way, they find new information about the number of short cycles (closed loops) in these noisy random lifts, extending previous work done on regular random graphs and random lifts. This helps to better understand the structure of these graphs and how they differ statistically.
polynomial threshold functionsrandom regular graphsrandom liftsnoisy random liftgraph hypothesis testingshort cycle countsd-regular graphlogarithmic cycle lengthrandom graph theory
Abstract
In this work, we present the first analysis of low degree polynomial threshold functions for the natural hypothesis testing problem of detecting the noisy random lift of a base $d$-regular graph from a uniformly random $d$-regular graph. Along the way, we obtain a new result for the distribution of short cycle counts in noisy random lift up to logarithmic lengths, which generalizes results by McKay, Wormald, and Wysocka and by Johnson in the case of random regular graphs, and the result by Fortin and Rudinsky in the case of random lift.