Skip to content
DraconiticResearch
Search Sources API
206,690 studies31 sourcesUpdated 27 min ago
PreprintarXiv licencearXiv

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

  • Xifan Yu
Open at sourcePDFDOICite

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 results by Greenhill, Janson, and Ruciński and by Fortin and Rudinsky in the case of random lifts.

Related

  1. Logarithmic asymptotics for polynomial threshold functions
    Martin Anthony
    arXivPreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv
  2. Improved polynomial-time algorithms for detecting and recovering planted Θ(√n)-cliques
    Dmitriy Kunisky, Songtao Mao
    arXivPreprintarXiv licenceFull textStatisticsarXiv
  3. Detecting adverse high-order drug combinations from individual case safety reports using computational statistics on disproportionality measures
    Jules Bangard, Einar Holsbø, Kristian Svendsen +2
    ComputoPeer-reviewedCC BY 4.0Full textStatisticsHAL
  4. Polynomial complexity, random graphs, and strict ergodicity
    Be'eri Greenfeld, Paul-Henry Leemann, Carlos Gustavo Moreira +1
    arXivPreprintarXiv licenceFull textCombinatorics & discrete mathematicsDynamical systemsarXiv
  5. Polynomial Sample Complexity of Noninteractive Simulation over Finite Alphabets
    Haoran Wang
    arXivPreprintarXiv licenceFull textGeneral mathematicsarXiv

Cite

BibTeXRIS
BibTeX
@misc{yu2026analysis,
  title = {{Analysis of Polynomial Threshold Functions on Random Regular Graphs: Computational Complexity of Detecting Noisy Random Lifts}},
  author = {Xifan Yu},
  howpublished = {arXiv},
  year = {2026},
  month = sep,
  doi = {10.48550/arxiv.2608.28539},
  eprint = {2608.28539},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2608.28539},
}
RIS
TY  - UNPB
TI  - Analysis of Polynomial Threshold Functions on Random Regular Graphs: Computational Complexity of Detecting Noisy Random Lifts
AU  - Xifan Yu
PY  - 2026
DA  - 2026/09/04
PB  - arXiv
DO  - 10.48550/arxiv.2608.28539
UR  - https://arxiv.org/abs/2608.28539
AB  - 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 results by Greenhill, Janson, and Ruciński and by Fortin and Rudinsky in the case of random lifts.
ER  -