Optimization, random graphs, and spin glasses
- This thesis studies a class of optimization problems on sparse random (hyper-)graphs. Of central focus is the optimum value of these problems on graphs with a large number of vertices. The first part introduces a general framework to study the typical value of some combinatorial optimization problems on sparse random graphs, via a connection with mean-field spin glasses. An an application, we derive novel bounds on various combinatorial quantities such as Max-Cut, min-bisection, max XORSAT etc. The second part of this thesis studies a semi-definite relaxation of the min-bisection problem on sparse random graphs. As a consequence, we provide near optimal recovery guarantees for a natural semi-definite programming based algorithm for the community detection problem.
|Type of resource
|electronic; electronic resource; remote
|1 online resource.
|Stanford University, Department of Statistics.
|Statement of responsibility
|Submitted to the Department of Statistics.
|Thesis (Ph.D.)--Stanford University, 2017.
- © 2017 by Subhabrata Sen
- This work is licensed under a Creative Commons Attribution Non Commercial 3.0 Unported license (CC BY-NC).
Also listed in
Loading usage metrics...