%0 Generic %1 sen2016optimization %A Sen, Subhabrata %D 2016 %K physics stats %T Optimization on Sparse Random Hypergraphs and Spin Glasses %U http://arxiv.org/abs/1606.02365 %X 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 Erd\Hos-Rényi and random regular graphs, Max XORSAT on Erd\Hos-Rényi hypergraphs, and the min-bisection for the Stochastic Block Model.

@misc{sen2016optimization, 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 Erd\H{o}s-R\'enyi and random regular graphs, Max XORSAT on Erd\H{o}s-R\'enyi hypergraphs, and the min-bisection for the Stochastic Block Model.}, added-at = {2018-09-12T07:07:05.000+0200}, author = {Sen, Subhabrata}, biburl = {https://www.bibsonomy.org/bibtex/2dba1f8d67a19f389ad35948d4c70ea0e/jeffxu}, interhash = {2ce92e35527133c53d42ca5aeabc4ebd}, intrahash = {dba1f8d67a19f389ad35948d4c70ea0e}, keywords = {physics stats}, note = {cite arxiv:1606.02365Comment: 28 pages}, timestamp = {2018-09-12T07:07:35.000+0200}, title = {Optimization on Sparse Random Hypergraphs and Spin Glasses}, url = {http://arxiv.org/abs/1606.02365}, year = 2016 }