Optimization on sparse random hypergraphs and spin glasses. Issue 3 (12th March 2018)

• Record Type: Journal Article
• Authors: Sen, Subhabrata
• Is Part Of: Random structures & algorithms. Volume 53:Issue 3(2018)
• Page Start: 504
• Page End: 536
• Publication Date: 2018-03-12
• Subjects: bisection -- optimization -- q‐cut -- spin glass -- XORSAT; Random graphs -- Periodicals; Mathematical analysis -- Periodicals; 519
• DOI: 10.1002/rsa.20774
• Languages: English
• ISSNs: 1042-9832

Abstract

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 graphs, Max XORSAT on Erdős–Rényi hypergraphs, and the min‐bisection the min‐bisection for the Stochastic Block Model.