The Lov\'asz Theta Function for Random Regular Graphs and Community Detection in the Hard Regime

DOI10.4230/LIPIcs.APPROX-RANDOM.2017.28zbMath1470.05143OpenAlexW3215143983MaRDI QIDQ5002631

Jess Banks, Moore, Cristopher, Robert D. Kleinberg

Publication date: 28 July 2021

Full work available at URL: http://drops.dagstuhl.de/opus/volltexte/2017/7577/pdf/LIPIcs-APPROX-RANDOM-2017-28.pdf

zbMATH Keywords

orthogonal polynomialsrandom regular graphssum of squaresLovász theta function

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Orthogonal functions and polynomials, general theory of nontrigonometric harmonic analysis (42C05) Coloring of graphs and hypergraphs (05C15)

Related Items (2)

Notes on computational-to-statistical gaps: predictions using statistical physics ⋮ On the computational tractability of statistical estimation on amenable graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Consistency thresholds for the planted bisection model
• Belief propagation, robust reconstruction and optimal recovery of block models
• Reconstruction and estimation in the planted partition model
• On the chromatic number of random regular graphs
• On the chromatic number of random \(d\)-regular graphs
• The expected eigenvalue distribution of a large regular graph
• A note on the sharp concentration of the chromatic number of random graphs
• Information-theoretic thresholds from the cavity method
• A proof of the block model threshold conjecture
• Nonbacktracking spectrum of random graphs: community detection and nonregular Ramanujan graphs
• Charting the replica symmetric phase
• Anneaux preordonnes
• Limit theorems for decomposable multi-dimensional Galton-Watson processes
• A Nullstellensatz and a Positivstellensatz in semialgebraic geometry
• Global Optimization with Polynomials and the Problem of Moments
• Sum-of-squares Lower Bounds for Planted Clique
• A nonparametric view of network models and Newman–Girvan and other modularities
• Spectral redemption in clustering sparse networks
• Achieving Exact Cluster Recovery Threshold via Semidefinite Programming: Extensions
• Achieving Exact Cluster Recovery Threshold via Semidefinite Programming
• NON-BACKTRACKING RANDOM WALKS MIX FASTER
• A proof of Alon’s second eigenvalue conjecture and related problems
• A Spectral Approach to Analysing Belief Propagation for 3-Colouring
• An approach to obtaining global extremums in polynomial mathematical programming problems
• On the Integrality Gap of Degree-4 Sum of Squares for Planted Clique
• Recovery and Rigidity in a Regular Stochastic Block Model
• Sum-of-squares proofs and the quest toward optimal algorithms
• The Computer Science and Physics of Community Detection: Landscapes, Phase Transitions, and Hardness
• Sum of squares lower bounds for refuting any CSP
• Community detection thresholds and the weak Ramanujan property
• Gibbs states and the set of solutions of random constraint satisfaction problems
• Additional Limit Theorems for Indecomposable Multidimensional Galton-Watson Processes
• Some remarks on the theory of graphs
• Approximation, Randomization, and Combinatorial Optimization.. Algorithms and Techniques

This page was built for publication: The Lov\'asz Theta Function for Random Regular Graphs and Community Detection in the Hard Regime