<div>Spectral Methods have had huge influence of modern algorithm design. For algorithmic problems on graphs, this is done by using a deep connection between random walks and the powers of various natural matrices associated with the graph. The major contribution</div><div>of this thesis initiates attempts to recover algorithmic results in Graph Minor Theory via spectral methods.</div><div><br></div><div>We make progress towards this goal by exploring these questions in the Property Testing Model for bounded degree graphs. Our main contributions are</div><div>1. The first result gives an almost query optimal one-sided tester for the property of H-minor-freeness. Benjamini-Schramm-Shapira (STOC 2008) conjectured that for fixed H, this can be done in time O(sqrt n). Our algorithm solves this in time n^{1/2+o(1)} which nearly resolves this upto n^{o(1)} factors.</div><div><br></div><div>2. BSS also conjectured that in the two-sided model, H-minor-freeness can be tested in time poly(1/eps). We resolve this conjecture in the affirmative.</div><div><br></div><div>3.Lastly, in a previous work on the two-sided-question above, Hassidim-Kelner-Nguyen-Onak (FOCS 2009) introduced a tool they call partition oracle. They conjectured that partition oracles could be implemented in time poly(1/eps) and gave an implementation which took exp(poly(1/eps)) time. In this work, we resolve this conjecture and produce such an oracle.</div><div><br></div><div><br></div><div>Additionally, this work also presents an algorithm which can recover a planted 3-coloring in a graph with some random like properties and suggests some future research directions alongside.</div>
| Identifer | oai:union.ndltd.org:purdue.edu/oai:figshare.com:article/12252191 |
| Date | 06 May 2020 |
| Creators | Akash Kumar (8802788) |
| Source Sets | Purdue University |
| Detected Language | English |
| Type | Text, Thesis |
| Rights | CC BY 4.0 |
| Relation | https://figshare.com/articles/Spectral_Approach_to_Modern_Algorithm_Design/12252191 |
Page generated in 0.0021 seconds