PaperlayerView exact revision on arXiv

Source-linked AI summary

Analysis of Polynomial Threshold Functions on Random Regular Graphs: Computational Complexity of Detecting Noisy Random Lift

Xifan Yu

arXiv:2608.28539v1math.COcs.CCcs.DS

TL;DR

The paper studies detecting a noisy random lift of a fixed regular graph from a uniformly random regular graph, a problem with limited computational-analysis techniques. It analyzes low-degree polynomial threshold functions and shows that logarithmic-degree symmetric functions cannot strongly detect noisy lifts of Ramanujan bases under small linear noise.

  • Problem

    The paper studies distinguishing a noisy random lift of a fixed d-regular graph from a uniformly random d-regular graph, a setting with limited computational lower-bound methods due to edge correlations.

    Source: §1 · p. 3

  • Method

    The paper develops a method for analyzing low-degree polynomials and polynomial threshold functions on random regular graphs.

    Source: §1 · p. 3

  • Results

    For Ramanujan bases, no Ω(log(n))-degree symmetric polynomial threshold function achieves strong detection under a small linear amount of noise, including the bipartite Ramanujan case.

    Source: §1.1 · p. 3

  • Takeaways & Limitations

    The results establish computational hardness for detecting noisy random lifts using symmetric polynomial threshold functions up to logarithmic degree.

    Source: §1.1 · p. 3

    The analysis does not establish hardness for higher-degree polynomials or threshold functions beyond logarithmic degree, where bicycles emerge and cycle-count assumptions fail.

    Source: §1.3 · p. 5

Abstract

from arXiv · show

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.

1 Introduction

The paper studies detecting noisy random lifts against uniformly random regular graphs and introduces methods for low-degree polynomials and polynomial threshold functions on random regular graphs. It establishes logarithmic-scale short-cycle Poisson limits and PTF hardness results supporting a conjectured computational barrier.

1 Introduction

  • The paper formulates noisy random-lift detection and introduces a method for analyzing low-degree polynomials and polynomial threshold functions on random regular graphs.The problem distinguishes a uniformly random d-regular graph from a noisy random lift of a fixed d-regular base graph H.Source: §1 · p. 3

1.1 Our Contribution

  • For Ramanujan bases, no Ω(log(n))-degree symmetric polynomial threshold function achieves strong detection, including the bipartite analogue for bipartite Ramanujan bases.This result provides further evidence for Conjecture 1.1, whose motivation includes certifying expansion, cut sizes, and independence number in random regular graphs [KY24].Source: §1.1 · p. 3

1.2 Related Works

  • Up to logarithmic lengths, noisy random-lift cycle counts converge in total variation to independent Poisson variables, extending prior random-regular-graph and noiseless-lift results.The convergence holds through D = Ω(log(n)), and through length 2D in the bipartite case; the proof uses a more involved Chen–Stein Poisson-approximation argument.Source: §1.1 · p. 4, §1.2 · p. 4

1.3 Open Questions

  • The paper asks whether hardness extends to higher-degree polynomials and PTFs, whether stronger sum-of-squares or local-statistical lower bounds hold, and whether faster-than-exp(Ω(n)) detection exists.At superlogarithmic degree, bicycles emerge, so arguments relying on symmetric low-degree polynomials being determined by cycle counts must change.Source: §1.3 · p. 5

2 Preliminaries

The preliminaries establish the graph, lift, and random-graph conventions used throughout the paper, then define noisy random lifts and the low-degree hypothesis-testing framework. They culminate in polynomial threshold functions as the broader algorithmic class studied.

2 Preliminaries

  • Graphs may be multigraphs with loops and parallel edges; degrees count loops twice, and d-regular and bipartite graphs are defined accordingly.Adjacency matrices count twice the number of loops on the diagonal and the number of parallel edges off the diagonal.Source: §2 · p. 5
  • An m-lift of a base graph H partitions km vertices into equal fibers so each base edge induces the corresponding regular bipartite structure between fibers.Half-loops are allowed in base graphs and contribute one to fiber degrees and adjacency-matrix diagonals.Source: §2 · p. 6

2.1 Configuration Model

  • The configuration model uniformly matches stubs to generate random regular graphs, while noisy random lifts first match lift stubs and then delete and uniformly rematch r selected edges.The noisy model hides the fiber partition using a uniformly random equitable relabelling, and r = 0 recovers the classical random lift.Source: §2.1 · pp. 6–7
  • The paper also defines noisy bipartite random lifts by matching across the base bipartition and rematching a uniformly selected set of edges within that bipartite structure.Random regular and random bipartite regular simple graphs are obtained by conditioning their respective configuration models on simplicity.Source: §2.1 · pp. 6–7

2.2 Computational Complexity of Hypothesis Testing

  • Hypothesis testing seeks a function distinguishing two distribution sequences, but computational analysis is motivated by the difficulty of likelihood-ratio testing and the gap between efficient and information-theoretic performance.The Low-Degree Conjecture links bounded low-degree advantage at degree at least log(n)^(1+ε) to the absence of polynomial-time strong detection, subject to its stated conditions.Source: §2.2 · p. 8
  • Bounded low-degree advantage rules out strong separation, which implies strong detection, while this work studies the more general degree-D polynomial threshold functions.A PTF outputs 1 when its degree-D polynomial is nonnegative and 0 otherwise.Source: §2.2 · p. 9

3 Main Results

The paper establishes degree-logarithmic PTF hardness for noisy lifts of Ramanujan bases, derives logarithmic-length Poisson limits for short cycles, and contrasts this with near-constant-degree detection for non-Ramanujan bases. It also proves statistical distinguishability for sufficiently low noise and explains the cycle-count mechanism underlying the hardness result.

3.1 PTF Hardness for Detecting Noisy Random Lift of Ramanujan Graph

  • For connected Ramanujan bases, no symmetric PTF of degree at most c log(n) achieves strong detection, including conditioned simple and bipartite settings.The hardness also extends to multigraph distributions and, via Jensen’s inequality, to degree-D polynomials.Source: §3.1 · p. 10

3.2 Distribution of Short Cycle Counts in Noisy Random Lift

  • Short cycle counts in noisy random lifts jointly converge to independent Poisson variables uniformly up to logarithmic lengths, generalizing prior random-regular and random-lift results.The theorem covers all lengths through D for general bases and even lengths through 2L for bipartite bases, with D,L ≤ c log(n).Source: §3.2 · pp. 10–11

3.3 Detecting Noisy Random Lift of Non-Ramanujan Graph is Easy

  • For non-Ramanujan bases, any diverging degree D = ω(1) suffices for a PTF to achieve strong detection when noise δ is at most a base-dependent constant Δ.The result applies to both ordinary and bipartite simple distributions, while constant-degree symmetric PTFs cannot achieve strong detection.Source: §3.3 · p. 12

3.4 Statistical Distinguishability of Noisy Random Lift

  • For every nontrivial base graph, sufficiently low-noise noisy random lifts are statistically distinguishable from random regular graphs.The theorem excludes a single vertex with d half-loops and, in the bipartite case, two vertices joined by d parallel edges.Source: §3.4 · p. 12

3.5 Proof Overview of the PTF Hardness Result

  • The hardness proof reduces symmetric low-degree PTFs to short cycle counts by peeling degree-1 vertices, using short-cycle disjointness, and proving Poisson convergence via Chen–Stein.Contiguity of the resulting cycle-count distributions then yields the PTF lower bound.Source: §3.5 · pp. 12–13

4 Tools for Configuration Model

This section establishes pairing-probability bounds for ordinary and bipartite configuration models, then applies them to bound subgraph occurrence probabilities in noisy random lifts. The noisy-lift analysis separates surviving lift edges from rematched noise edges and combines bounds for both parts.

Lemma 4.1

  • For e=o(n) disjoint stub-pairs, the probability that all prescribed pairs occur in a uniformly random configuration-model matching is bounded using uniform perfect-matching probabilities.The analogous statement holds for e=o(n1+n2) prescribed pairs in a bipartite configuration model.Source: §4 · p. 13

Lemma 4.2

  • Lemma 4.2 bounds the probability that a simple graph F with o(n) edges appears in a noisy random lift of a fixed d-regular base graph, with an analogous bipartite result.The hypotheses include d≥3, δ∈[0,1], and no isolated vertices in F; the bound uses a constant K depending on the base graph H.Source: §4 · p. 14

Proof of Lemma 4.2

  • The proof decomposes the noisy lift as G=GO⊔GR, where GO contains retained lift-pairs and GR contains noise-pairs created by rematching stubs exposed by random edge deletion.A union bound over subgraphs A⊆F assigns A to GO and F\A to GR.Source: §4 · p. 14
  • The lift contribution is bounded via Lemma 4.1, while the noise contribution requires deleting incident stub-pairs and then rematching the exposed stubs; combining these conditional bounds yields the result.If more incident stub-pairs must be deleted than the available r deleted edges, the relevant probability is zero; otherwise deletion and rematching probabilities are bounded before a union bound over realizations.Source: §4 · pp. 14–15

5 Proof of PTF Hardness

This section proves the polynomial-structure reductions and probabilistic facts needed to establish logarithmic-degree PTF hardness for detecting noisy random lifts of Ramanujan graphs. It further transfers the hardness to related graph distributions and extends the impossibility from symmetric threshold functions to all low-degree polynomials under permutation invariance.

5 Proof of PTF Hardness

  • The proof of Theorem 3.2 is assembled from Theorem 3.6, Corollaries 3.3–3.4, and a reduction of symmetric polynomial tests on regular simple graphs.The section begins by reviewing the polynomial space and then develops the auxiliary results needed for the hardness proof.Source: §5 · p. 16

5.1 Polynomials on Regular Simple Graph

  • Every degree-D polynomial on d-regular simple graphs reduces to multilinear adjacency-matrix polynomials, while symmetric polynomials are spanned by unlabeled subgraph-count polynomials and, modulo regularity constraints, by K≤D.Lemma 5.3 establishes that each f ∈ Rsym[Y ]≤D has an equivalent g ∈ K≤D modulo the constraints of d-regular simple graphs.Source: §5.1 · pp. 16–17

5.2 Auxillary Results

  • For D ≤ c log(n), the rare-event probability R≤D is o(1) under Q_S, P_S, Q_b,S, and P_b,S, so short bicycles are absent with high probability.On the complementary good event, short cycles are vertex-disjoint, enabling factorization of subgraph counts.Source: §5.2 · pp. 18–19
  • On G ∈ R^c≤2D, every nonzero Nα(Y ) for α ∈ G≤D with minimum degree at least 2 corresponds to a disjoint union of cycles and is an explicit polynomial in Z3, …, ZD.Thus every f ∈ K≤D becomes a function of short cycle counts on the good event.Source: §5.2 · pp. 19–20
  • For a Ramanujan base graph, the non-backtracking matrix B has one eigenvalue d − 1, while every other eigenvalue has absolute value at most d − 1.In the bipartite case, B has eigenvalues d − 1 and −d + 1.Source: §5.2 · pp. 21–22

5.3 Proof of Theorem 3.2

  • For D ≤ c2 log(n), Theorem 3.6 gives convergence of short cycle counts to independent Poissons under both Q and P, providing the distributional comparison used in proving Theorem 3.2.The proof then conditions on simplicity and expresses the resulting laws through LQS(Z3, …, ZD) and LPS(Z3, …, ZD).Source: §5.3 · p. 23
  • For Ramanujan H, no symmetric PTF of degree at most c(H) log(n) achieves strong detection between QS and PS.The bipartite Ramanujan case follows by the same argument.Source: §5.3 · p. 24

5.4 Proof of the Corollaries

  • Theorem 3.2’s hardness transfers to Q and P, and likewise to their bipartite versions Qb and Pb, because the corresponding random graph models are simple with probability bounded away from zero.The contradiction argument assumes a strongly detecting symmetric PTF for the target distributions and derives one contradicting Theorem 3.2.Source: §5.4 · p. 24
  • Permutation averaging and Jensen’s inequality show that any degree-at-most-D polynomial strongly separating QS and PS would yield a symmetric PTF doing so, contradicting Theorem 3.2.Therefore no polynomial of degree at most D achieves strong separation, with the same proof applying to the bipartite versions.Source: §5.4 · pp. 24–25

6 Proof of Distribution of Short Cycle Counts

This section proves the distributional result for short cycle counts in noisy random lifts using a Chen–Stein analysis of local cycle configurations and their dependencies. It bounds the relevant dependency terms, computes the cycle-count means, and concludes the result for logarithmic lengths in both non-bipartite and bipartite cases.

6 Proof of Distribution of Short Cycle Counts

  • The proof applies Chen–Stein Poisson approximation to local-configuration indicators, with dependency neighborhoods formed by configurations sharing stubs.For lengths t ≤ D, every cycle has a unique realized local configuration, so the cycle count Z_t is represented by the sum of these indicators.Source: §6 · pp. 25, 28, 29
  • Local configurations record cycle vertices, consecutive stub pairs, original-retained or rematched edge types, and deleted original pairs supporting rematching.Feasibility requires distinct original stubs and specific incidence relations between deleted and rematched pairs; realization depends on the underlying lift, deletion, and rematching processes.Source: §6 · p. 26
  • Fact 6.1 gives the exact probability that a feasible local configuration is realized, with probability zero when edel(α) > r.The formula combines noiseless-lift pairing probabilities with deletion, retention, and rematching probabilities.Source: §6 · p. 28

6.1 Bound for b1

  • For b1, the dependency contribution is o(1) when D ≤ c1 log(n), using bounds on configuration counts and stub neighborhoods.The argument uses ρ(α) ≤ t, edel(α) ≤ 2ρ(α), and |stub(α)| ≤ 4t ≤ 4D.Source: §6.1 · pp. 31–32

6.2 Bound for b2

  • For b2, compatible overlapping configurations satisfy stricter relations among retained, deleted, and rematched pairs, including either a reduced total cycle-pair count or an additional deleted pair.Compatibility requires shared stub pairs to be identical and consistently typed, while the joint realization probability is bounded analogously to Fact 6.1.Source: §6.2 · pp. 32–33
  • For b2, compatible cycle pairs are enumerated by their shared stub-pairs and structural parameters, yielding a bound that is o(1) when D ≤ c2 log(n).The enumeration distinguishes intersecting and disjoint cycle stub-pairs and uses the constraints max{s,t} ≤ h+q ≤ s+t and h ≤ f ≤ 2h.Source: §6.2 · pp. 34–36

6.3 Bound for b3

  • For b3, the total variation term is rewritten as a coupling problem between the noisy-lift configuration conditioned on Xα = 1 and its unconditional distribution.The coupling is constructed on feasible triples (Oret,Odel,R), representing retained, deleted, and rematched stub-pairs.Source: §6.3 · p. 37
  • The coupling construction uses four types of primitive switching operations and proceeds through the O, ret/del, and R stages, each specified as part of the construction.Source: §6.3 · pp. 38, 40
  • Across the O, ret/del, and R stages, switching can alter configurations outside N(α) only through a swapped stub-pair, whose conditional distribution is uniform over unconditioned pairs.The support switchings preserve realizations outside N(α), while the remaining changes are bounded using the uniformity of swapped pairs and the available stub counts.Source: §6.3 · pp. 42, 43, 47
  • The b3 contribution is o(1) provided D ≤ c3 log(n), for a constant c3 = c3(H) > 0.The bound combines estimates from the O, ret/del, and R switching stages for every local configuration α ∈ I.Source: §6.3 · pp. 49–50

6.4 Mean Computation

  • The expected number µt of length-t cycles is established by summing probabilities over typed stub-pair sequences, separately treating all-original-retained and rematched configurations.The derivation accounts for the 2^t trace overcounting factor and obtains µt for a constant K7 = K7(H) > 0.Source: §6.4 · pp. 55, 56, 58

6.5 Concluding the Proof

  • For the non-bipartite case, choosing c(H) as the minimum of the established constants and applying the preceding bounds proves Theorem 3.6 for all D ≤ c log(n).The argument uses KL divergence for product Poisson distributions and Pinsker’s inequality to obtain the required approximation.Source: §6.5 · p. 60
  • The bipartite case follows by essentially the same proof, with minor adjustments to the mean computation.Source: §6.5 · p. 60

7 Proof of Detection for Non-Ramanujan Noisy Lift

The section proves strong detection for non-Ramanujan noisy lifts by exploiting a non-backtracking eigenvalue induced by an outlying base-graph eigenvalue and separating corresponding cycle-count distributions. It also shows that non-constant degree is necessary for this PTF-based strong detection.

7 Proof of Detection for Non-Ramanujan Noisy Lift

  • A non-Ramanujan eigenvalue ρ with |ρ| > 2 induces a weighted non-backtracking eigenvalue λ satisfying λ^2 − λρ + d − 1 = 0.The induced eigenvalue provides the spectral growth needed for detection.Source: §7 · pp. 60–61
  • Choosing δ = δ(H) > 0 so that (1 − δ)^2λ^2 > d − 1 yields separated upper and lower Poisson tail thresholds for any D = ω(1).The proof applies Theorem 3.6 for D ≤ c log(n), with c = c(H) > 0.Source: §7 · pp. 61–62
  • For any D = ω(1), thresholding the number of length-D cycles achieves strong detection between PS and QS for every δ ≤ ∆(H), for some ∆(H) > 0.The threshold is chosen using the separated Poisson cycle-count distributions.Source: §7 · p. 62
  • The bipartite case follows by an essentially identical argument and is omitted.Source: §7 · p. 62
  • Non-constant degree is necessary because products of Poisson limits for cycle counts under P and Q are contiguous when the degree is constant.Source: §7 · p. 62

8 Proof of Statistical Distinguishability

Theorem 3.10 is proved by counting stub-pair realizations: noisy random lifts occupy an exponentially smaller set of simple graphs than the random-regular-graph support, yielding statistical distinguishability.

Counting argument

  • The proof bounds noisy-lift realizations by enumerating fiber partitions, stub types, deleted-stub choices, rematchings, and retained noiseless-lift pairings.The retained-pairing factor is controlled by comparing the noiseless lift before deletion with the loss from r deleted edges, for sufficiently small δ.Source: §8 · p. 63
  • The noisy random lift’s possible simple-graph realizations are exponentially fewer than those under Q_S, so most of Q_S’s support lies outside P_S.For sufficiently small δ = δ(H) > 0, the counting argument concludes statistical distinguishability.Source: §8 · p. 65

Case analysis

  • For the non-bipartite case, the argument assumes a d-regular base graph H that is not a single vertex with d half-loops.The bipartite case is omitted and stated to follow by a similar counting argument.Source: §8 · p. 65
Loading 2608.28539v1…