Expansion in Lifts of Graphs.
The central goal of this thesis is to better understand, and explicitly construct, expanding towers G_1,G_2,..., which are expander families with the additional constraint that G_{n+1} is a lift of G_n. A lift G of H is a graph that locally looks like H, but globally may be different; lifts have bee...
Disimpan dalam:
| Pengarang Utama: | |
|---|---|
| Pengarang Korporat: | |
| Format: | Buku |
| Bahasa: | English |
| Subjek-subjek: | |
| Penanda-penanda: |
Tambah Penanda
Tiada Penanda, Jadilah orang pertama menanda rekod ini!
|
| LEADER | 02259nam a2200301 i 4500 | ||
|---|---|---|---|
| 001 | 014347115-5 | ||
| 005 | 20150410020426.0 | ||
| 008 | 150410s2015 mau m 000|0|eng|d | ||
| 035 | 0 | |a ocn907856129 | |
| 035 | |a (DASH)14398532 | ||
| 040 | |a MH |b eng |e rda |c MH | ||
| 100 | 1 | |a Makelov, Aleksandar A., |e author. | |
| 245 | 1 | 0 | |a Expansion in Lifts of Graphs. |
| 264 | 0 | |c 2015. | |
| 336 | |a text |b txt |2 rdacontent | ||
| 337 | |a computer |b c |2 rdamedia | ||
| 338 | |a online resource |b cr |2 rdacarrier | ||
| 502 | |b AB |c Harvard University |d 2015. | ||
| 502 | |a Thesis (AB)--Computer Science, Harvard College, May 2015. | ||
| 520 | 3 | |a The central goal of this thesis is to better understand, and explicitly construct, expanding towers G_1,G_2,..., which are expander families with the additional constraint that G_{n+1} is a lift of G_n. A lift G of H is a graph that locally looks like H, but globally may be different; lifts have been proposed as a more structured setting for elementary explicit constructions of expanders, and there have recently been promising results in this direction by Marcus, Spielman and Srivastava [MSS13], Bilu and Linial [BL06], and Rozenman, Shalev and Wigderson [RSW06]; besides that, expansion in lifts is related to the Unique Games Conjecture (e.g., Arora et al [AKK+08]). | |
| 520 | 8 | |a We develop the basic theory of spectral expanders and lifts in the generality of directed multigraphs, and give some examples of their applications. We then derive some group-theoretic structural properties of towers, and show that a large class of commonly used graph operations "respect" lifts. These two insights allow us to give a different perspective on an existing construction [RSW06], show that standard iterative constructions of expanders can be adjusted to give expander towers almost "for free", and give a new elementary construction, along the lines of Ben-Aroya and Ta-Shma [BATS11], of a fully-explicit expanding tower of almost optimal spectral expanders. | |
| 653 | 0 | 0 | |a Mathematics. |
| 653 | 0 | 0 | |a Computer Science. |
| 655 | 7 | |a Theses. |2 aat | |
| 710 | 2 | |a Harvard School of Engineering and Applied Sciences. |t Senior honors thesis. | |
| 710 | 2 | |a Harvard University, |e degree granting institution. | |
| 988 | |a 20150410 | ||
| 906 | |0 MH | ||