Optimization on sparse random hypergraphs and spin glasses

DOI10.1002/RSA.20774MaRDI QIDQ4961546zbMATH OpenOpenAlexWikidataFDO

Authors Subhabrata Sen

Publication date 25 October 2018

Published in Random Structures \& Algorithms (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1606.02365

zbMATH Keywords

\(q\)-cutbisectionoptimizationspin glassXORSAT

Mathematics Subject Classification ID

Density (toughness, etc.) (05C42) Hypergraphs (05C65) Random graphs (graph-theoretic aspects) (05C80) Combinatorial optimization (90C27)

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 $q$-cut on ErdH{o}s-R'enyi and random regular graphs, Max XORSAT on ErdH{o}s-R'enyi hypergraphs, and the min-bisection for the Stochastic Block Model.

Recommendations

• Central limit theorems for combinatorial optimization problems on sparse Erdős-Rényi graphs
• On the maximal cut in a random hypergraph
• On the max-cut of sparse random graphs
• Suboptimality of local algorithms for a class of max-cut problems

Cited in

(20)

• MAX \(\kappa\)-cut and the inhomogeneous Potts spin Glass
• Posterior agreement for large parameter-rich optimization problems
• On the unbalanced cut problem and the generalized Sherrington-Kirkpatrick model
• Optimization of mean-field spin glasses
• Approximate ground states of hypercube spin glasses are near corners
• scientific article; zbMATH DE number 558545 (Why is no real title available?)
• Optimal couplings between sparse block models
• Combinatorics. Abstracts from the workshop held January 1--7, 2023
• On the minimum bisection of random 3-regular graphs
• A Friendly Tutorial on Mean-Field Spin Glass Techniques for Non-Physicists
• Optimizing mean field spin glasses with external field
• Phase transitions for greedy sparse approximation algorithms
• Parisi formula for balanced Potts spin glass
• The landscape of the planted clique problem: dense subgraphs and the overlap gap property
• The fractional chromatic number of random graphs
• Partial recovery and weak consistency in the non-uniform hypergraph stochastic block model
• Bounds on the ground state energy of quantum p-spin Hamiltonians
• Densest subgraphs of a dense Erdös-Rényi graph. Asymptotics, landscape, and universality
• Color symmetry breaking in the Potts spin glass
• On the MCMC performance in Bernoulli group testing and the random max-set cover problem

This page was built for publication: Optimization on sparse random hypergraphs and spin glasses

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4961546)