Optimization, random graphs, and spin glasses
Abstract/Contents
- Abstract
- 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.
Description
| Type of resource | text |
|---|---|
| Form | electronic; electronic resource; remote |
| Extent | 1 online resource. |
| Publication date | 2017 |
| Issuance | monographic |
| Language | English |
Creators/Contributors
| Associated with | Sen, Subhabrata |
|---|---|
| Associated with | Stanford University, Department of Statistics. |
| Primary advisor | Dembo, Amir |
| Primary advisor | Montanari, Andrea |
| Thesis advisor | Dembo, Amir |
| Thesis advisor | Montanari, Andrea |
| Thesis advisor | Chatterjee, Sourav |
| Advisor | Chatterjee, Sourav |
Subjects
| Genre | Theses |
|---|
Bibliographic information
| Statement of responsibility | Subhabrata Sen. |
|---|---|
| Note | Submitted to the Department of Statistics. |
| Thesis | Thesis (Ph.D.)--Stanford University, 2017. |
| Location | electronic resource |
Access conditions
- Copyright
- © 2017 by Subhabrata Sen
- License
- This work is licensed under a Creative Commons Attribution Non Commercial 3.0 Unported license (CC BY-NC).
Also listed in
Loading usage metrics...