The Lovász Theta Function for Random Regular Graphs and Community Detection in the Hard Regime
From MaRDI portal
Publication:5232321
DOI10.1137/18M1180396zbMath1420.05160arXiv1705.01194OpenAlexW2964325226MaRDI QIDQ5232321
Jess Banks, Moore, Cristopher, Robert D. Kleinberg
Publication date: 2 September 2019
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1705.01194
graph coloringrandom graphscommunity detectionsemidefinite relaxationsum-of-squares proofsplanted partitions
Random graphs (graph-theoretic aspects) (05C80) Semidefinite programming (90C22) Stochastic network models in operations research (90B15) Coloring of graphs and hypergraphs (05C15)
Related Items (3)
Disordered systems insights on computational hardness ⋮ Computational barriers to estimation from low-degree polynomials ⋮ Mean estimation with sub-Gaussian rates in polynomial time
Cites Work
- Unnamed Item
- Unnamed Item
- Consistency thresholds for the planted bisection model
- Reconstruction and estimation in the planted partition model
- Improved approximation algorithms for MAX \(k\)-cut and MAX BISECTION
- 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
- Charting the replica symmetric phase
- Spectra of regular graphs and hypergraphs and orthogonal polynomials
- 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
- Exact Recovery in the Stochastic Block Model
- Quiet Planting in the Locked Constraint Satisfaction Problems
- NON-BACKTRACKING RANDOM WALKS MIX FASTER
- A proof of Alon’s second eigenvalue conjecture and related problems
- Random matrices, nonbacktracking walks, and orthogonal polynomials
- A Spectral Approach to Analysing Belief Propagation for 3-Colouring
- An approach to obtaining global extremums in polynomial mathematical programming problems
- Approximate graph coloring by semidefinite programming
- On the Shannon capacity of a graph
- Community Detection and Stochastic Block Models
- Proof of the Achievability Conjectures for the General Stochastic Block Model
- 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
- A Nearly Tight Sum-of-Squares Lower Bound for the Planted Clique Problem
- 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
- Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques
- Semidefinite programs on sparse random graphs and their application to community detection
- Gibbs states and the set of solutions of random constraint satisfaction problems
- Additional Limit Theorems for Indecomposable Multidimensional Galton-Watson Processes
- The Lovász Number of Random Graphs
- Some remarks on the theory of graphs
- The two possible values of the chromatic number of a random graph
This page was built for publication: The Lovász Theta Function for Random Regular Graphs and Community Detection in the Hard Regime
