Optimization on Sparse Random Hypergraphs and Spin Glasses
arXiv:1606.02365
Abstract
We establish that in the large degree limit, the value of certain optimization problems on sparse random hypergraphs is determined by an appropriate Gaussian optimization problem. This approach was initiated in Dembo et. al.(2016) for extremal cuts of graphs. The usefulness of this technique is further illustrated by deriving the optimal value for Max -cut on Erdős-Rényi and random regular graphs, Max XORSAT on Erdős-Rényi hypergraphs, and the min-bisection for the Stochastic Block Model.
arXiv comment28 pages
References in corpus (12)
- Asymptotic analysis of the stochastic block model for modular networks and its algorithmic applications
- Gibbs States and the Set of Solutions of Random Constraint Satisfaction Problems
- The largest eigenvalue of rank one deformation of large Wigner matrices
- Extremal Cuts of Sparse Random Graphs
- A simple invariance theorem
- A Dynamic Programming Approach to the Parisi Functional
- Suboptimality of local algorithms for a class of max-cut problems
- Maximum independent sets on random regular graphs
- On the -sat model with large number of clauses
- On the unbalanced cut problem and the generalized Sherrington-Kirkpatrick model
- The minimum bisection in the planted bisection model
- The K-sat problem in a simple limit
Cited by in corpus (5)
- Suboptimality of local algorithms for a class of max-cut problems
- A connection between MAX -CUT and the inhomogeneous Potts spin glass in the large degree limit
- The marginally stable Bethe lattice spin glass revisited
- On the -sat model with large number of clauses
- Disorder chaos in some diluted spin glass models