Source-linked AI summary
Analysis of Polynomial Threshold Functions on Random Regular Graphs: Computational Complexity of Detecting Noisy Random Lift
Xifan Yu
TL;DR
The paper studies distinguishing a uniformly random d-regular graph from a noisy random lift, a setting where edge correlations limit existing computational lower-bound methods. It develops an approach for low-degree polynomials and polynomial threshold functions, showing strong limitations for symmetric PTFs under Ramanujan assumptions and identifying open challenges beyond logarithmic degree.
Problem
The paper studies distinguishing a uniformly random d-regular graph from a noisy random lift, a hypothesis-testing problem whose edge correlations place it outside usual average-case computational analyses.
Method
The paper develops a new method for analyzing low-degree polynomials and polynomial threshold functions on random regular graphs.
Results
For Ramanujan base graphs, no Ω(log(n))-degree symmetric polynomial threshold function achieves strong detection between random regular graphs and lightly corrupted random lifts.
Takeaways & Limitations
The analysis reduces the relevant nonzero subgraph contributions to disjoint unions of cycles and establishes that two specified graph classes occur with probability o(1).
Takeaways & Limitations
The open problem remains to establish hardness against higher-degree polynomials and PTFs, since bicycles emerge at superlogarithmic scale and invalidate the cycle-count assumption.
Abstract
from arXiv · showhide
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 develops low-degree polynomial and PTF analyses for this setting. It establishes PTF hardness and logarithmic-scale Poisson cycle-count results, while identifying higher-degree analysis as an open direction.
- The hypothesis-testing problem distinguishes a uniformly random d-regular graph from a noisy random lift of a fixed base d-regular graph.
- Existing computational analyses of random regular graphs are limited, partly because edge correlations undermine standard average-case lower-bound techniques.
- The paper introduces a method for analyzing low-degree polynomials and polynomial threshold functions on random regular graphs.
- No Ω(log(n))-degree symmetric PTF achieves strong detection for Ramanujan bases, with analogous hardness for bipartite Ramanujan bases.
- Cycle counts up to logarithmic lengths converge to products of independent Poisson distributions in noisy random lifts, including the bipartite extension up to length 2D.
- The noisy-lift cycle result generalizes prior random-regular-graph and noiseless-lift results, using a more involved Chen–Stein Poisson-approximation proof.
- Higher-degree hardness remains open because bicycles emerge at superlogarithmic scale, undermining the cycle-count characterization of symmetric low-degree polynomials.
2 Preliminaries
The preliminaries define the graph, lift, configuration-model, noisy-lift, and hypothesis-testing frameworks used throughout the paper.
- Graph terminology: A graph is d-regular when every vertex has degree d; loops contribute two and half-loops contribute one to degree.Simple graphs have neither loops nor parallel edges, while half-loops appear only in base graphs of lifts.
- Graph lifts: An m-lift of a base graph H partitions its km vertices into equal fibers, with each base edge represented by the corresponding regular bipartite structure.The base graph is H, and the fiber of i is σ^-1(i).
- Configuration models: The configuration model creates vertices' stubs according to a degree sequence, uniformly matches all stubs, and joins matched pairs into edges.The bipartite version separately creates L- and R-stubs and uniformly matches the two sides.
- Noisy random lifts: A noisy random lift first samples an m-lift of H, then deletes a uniformly random subset of r edges and uniformly rematches their exposed stubs.The model hides the fiber partition through a uniformly random relabelling; r = 0 gives the classical random lift.
- Noisy random lifts: The same construction has a bipartite variant that preserves the bipartition when matching the exposed stubs after edge deletion.Its initial lift matches stubs only across the two parts, and the rematching also pairs the two exposed sides.
- Hypothesis testing: The paper studies strong detection between two distribution sequences using a function on an n-polynomial-dimensional space, motivated by the difficulty of computing likelihood-ratio tests.Without computational restrictions, the likelihood-ratio test is statistically optimal, but efficient algorithms may not attain information-theoretic limits.
3 Main Results
The paper establishes logarithmic-degree PTF hardness for detecting noisy lifts of Ramanujan graphs, contrasts it with barely nonconstant-degree detection for non-Ramanujan bases, and analyzes short-cycle distributions up to logarithmic lengths.
- Problem setup: The model tests a uniformly random d-regular graph against a noisy random lift of a fixed d-regular base graph, with simple-graph distributions obtained by conditioning on simplicity.The bipartite analogue uses random bipartite d-regular graphs and noisy bipartite lifts.
- PTF hardness for Ramanujan lifts: For a Ramanujan base graph, no symmetric PTF of degree at most c log(n) achieves strong detection.The result applies to bases potentially having half-loops and has a bipartite counterpart.
- PTF hardness for Ramanujan lifts: The same Ramanujan-case hardness applies to multigraph distributions and extends from symmetric PTFs to degree-D polynomials.The polynomial extension follows from a Jensen’s inequality argument.
- Distribution of short cycle counts: Short cycle counts under noisy random lift converge jointly to independent Poisson distributions uniformly up to logarithmic lengths, providing a key proof ingredient.This generalizes prior random-regular and random-lift results.
- Distribution of short cycle counts: Both noisy random lifts and random regular graphs are simple with probability bounded below by a positive constant depending on the base graph.The statement covers both ordinary and bipartite settings.
- Detection for non-Ramanujan lifts: For a non-Ramanujan base, a PTF of any degree D = ω(1) achieves strong detection for sufficiently small noise, while constant-degree symmetric PTFs cannot.The result is stated as optimal in its degree dependence and pins down the exact PTF complexity in this setting.
- Statistical distinguishability: For nontrivial bases and sufficiently small noise, the noisy-lift and random-regular distributions are statistically distinguishable.Separate statements cover ordinary and bipartite bases with specified excluded cases.
4 Tools for Configuration Model
The configuration-model toolkit bounds probabilities of prescribed small subgraphs by decomposing noisy lifts into retained lift edges and rematched noise edges.
- Configuration-model pairing bounds: The configuration model pairs stubs through a uniformly random perfect matching, with an analogous uniformly random bipartite matching between left and right stubs.These bounds apply to collections of o(n) disjoint stub-pairs, or o(n1+n2) bipartite stub-pairs.
- Noisy-lift decomposition: A noisy lift is formed by generating a noiseless lift, deleting r uniformly chosen edges, and rematching the exposed stubs using the configuration model.The resulting graph decomposes into retained lift-pairs and noise-pairs.
- Subgraph probability bounds: For a small target subgraph F, the proof sums over decompositions F = A ∪ (F \ A), where A lies among retained lift edges and F \ A among rematched noise edges.The argument first bounds A ⊆ GO, then conditionally bounds F \ A ⊆ GR.
- Subgraph probability bounds: The number of stub-pair realizations contributes factors bounded using the degree, while deletion and rematching probabilities control the noise-edge contribution.If the required incident stub-pairs exceed the number of deleted edges, the conditional probability is zero.
- Bipartite extension: The bipartite proof follows the same structure with adjustments for bipartite configuration models, and its details are omitted.The paper explicitly characterizes this as an essentially identical proof.
5 Proof of PTF Hardness
The proof reduces symmetric low-degree polynomials on regular graphs to cycle-count polynomials, then uses short-cycle behavior to establish PTF hardness up to logarithmic degree.
- Polynomial spaces: Symmetric polynomials are spanned by subgraph-count polynomials indexed by unlabelled graphs with at most D edges and no isolated vertices.The polynomial space uses multilinear monomials indexed by subgraphs of the complete graph.
- Polynomial spaces: Any symmetric polynomial of degree at most D is equivalent modulo regularity constraints to a polynomial in the subspace generated by graphs of minimum degree at least 2.The reduction proceeds inductively by eliminating leaves from subgraph-count polynomials.
- Cycle-count reduction: For D ≤ c(H) log(n), the relevant rare-event probabilities are o(1) under simple random regular and bipartite graph distributions.The same logarithmic-length control supports the reduction used in the hardness argument.
- Cycle-count reduction: With high probability, nonzero reduced subgraph counts of minimum degree at least 2 are disjoint unions of cycles, so they become polynomials of the short cycle counts.The proof excludes connected components with more edges than vertices and factors counts for disjoint cycle unions.
- Spectral input: The base graph’s non-backtracking spectrum yields one eigenvalue d−1, while all other eigenvalues have absolute value at most d−1 under the Ramanujan condition.These spectral bounds control traces of powers of the weighted non-backtracking matrix.
- Hardness conclusion: For Ramanujan base graphs, no Ω(log(n))-degree symmetric PTF achieves strong detection between random regular graphs and noisy random lifts.The result also extends to bipartite Ramanujan bases and to multigraph distributions.
6 Proof of Distribution of Short Cycle Counts
The proof models short cycles through local stub configurations and applies Chen–Stein Poisson approximation to show joint convergence of cycle counts under noisy lifts.
- Poisson approximation: Chen–Stein Poisson approximation is applied to indicators of local configurations for cycles of lengths up to D.The setup partitions configuration indicators by cycle length and aggregates them into cycle-count variables.
- Model setup: The analysis fixes the fiber partition because cycle counts are invariant under vertex relabelling, then studies the resulting noisy-lift model.The fixed-partition model has the same cycle-count distribution as the uniformly partitioned model.
- Local configurations: A local configuration records cycle vertices, consecutive stub pairs, and whether edges are retained from the noiseless lift or created by rematching.Rematched pairs additionally record the original deleted stub pairs.
- Local configurations: Feasibility imposes distinct original stubs, matching-class partitions, and relations among retained, deleted, and rematched pairs.These relations determine the combinatorial parameters used in the probability and dependency estimates.
- Counting cycles: Each feasible configuration has an exact realization probability, while configurations with more than r deleted pairs have probability zero.Every length-t cycle has a unique realized local configuration, so the aggregate variable counts cycles exactly.
7 Proof of Detection for Non-Ramanujan Noisy Lift
For non-Ramanujan bases, a nontrivial adjacency eigenvalue produces an amplified non-backtracking eigenvalue, making sufficiently long cycle counts distinguish noisy lifts from random regular graphs.
- Spectral mechanism: A non-Ramanujan base has an adjacency eigenvalue ρ ≠ d with |ρ| > 2√(d−1), generating a nontrivial non-backtracking eigenvalue.The eigenvalues satisfy λ^2 − λρ + d − 1 = 0.
- Spectral mechanism: The non-backtracking matrix has the leading eigenvalue d−1 and another eigenvalue exceeding √(d−1) in magnitude.This separates the non-Ramanujan spectral contribution from the bulk scale.
- Detection: Choosing δ sufficiently small ensures the noisy-lift spectral contribution dominates the random-regular scale for any D = ω(1).The condition used is (1 − δ)^2 λ^2 > d − 1.
- Detection: A PTF thresholding the number of length-D cycles achieves strong detection between noisy lifts and random regular graphs for sufficiently small noise.The proof extends essentially identically to the bipartite case.
- Scope boundary: Non-constant degree is necessary because fixed-degree cycle-count limits are contiguous under both distributions.Thus constant-degree PTFs cannot obtain strong detection through these limiting cycle counts.
8 Proof of Statistical Distinguishability
The statistical distinguishability proof counts graph realizations and shows that, for sufficiently small noise, noisy random lifts occupy an exponentially smaller support than random regular graphs.
- Counting realizations: The proof uses a counting argument for noisy-lift stub-pair realizations, separating fiber assignments, stub types, deletions, rematching, and retained pairs.Each factor bounds one stage of constructing a noisy lift.
- Comparison of supports: Random regular graphs have (dn−1)!! potential stub-pair realizations, with a bounded-away-from-zero fraction corresponding to simple graphs.Dividing by (d!)^n converts stub-pair counts into simple-graph counts.
- Counting realizations: Small noise preserves enough available stub pairings to obtain an exponential upper bound on noisy-lift realizations.The argument assumes r = δdn/2 is sufficiently small relative to the fiber size.
- Comparison of supports: For sufficiently small δ, the noisy-lift support is exponentially smaller than the total support under random regular graphs.This yields the stated statistical distinguishability conclusion; the bipartite case follows similarly.