PhD Defence • Algorithms and Complexity — Higher Order Random Walks, Local Spectral Expansion, and ApplicationsExport this event to calendar

Tuesday, August 18, 2020 — 1:00 PM EDT

Please note: This PhD defence will be given online.

Vedat Levi Alev, PhD candidate
David R. Cheriton School of Computer Science

The study of spectral expansion of graphs and expander graphs has been an extremely fruitful line of research in Mathematics and Computer Science, with applications ranging from random walks and fast sampling to optimization. In this dissertation, we study high dimensional local spectral expansion, which is a generalization of the theory of spectral expansion of graphs, to simplicial complexes.

We study two random walks on simplicial complexes, which we call the down-up walk, which captures a wide array of natural random walks which can be used to sample random combinatorial objects via the so-called heat-bath dynamics, and the swap walk, which can be thought as a random walk on a sparse version of the Kneser graph.

We prove a sharp bound on the second eigenvalue of the down-up walk and discuss applications of this in establishing the rapid mixing of several Markov chains used for sampling combinatorial objects.

Next, we study the spectrum of the swap walks, and show that using local spectral expansion we can relate the spectrum of swap-walk on any simplicial complex to the spectrum of the Kneser graph. We will mention applications of this result in (i) approximating constraint satisfaction problems (CSPs) on instances where the constraint hypergraph is a high dimensional local spectral expander; and in (ii) the construction of new families of list decodable codes based on (sparse) Ramanujan complexes of Lubotzky, Samuels, and Vishne. 

Location 
Online PhD defence
200 University Avenue West

Waterloo, ON N2L 3G1
Canada

S M T W T F S
27
28
29
30
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
  1. 2020 (188)
    1. November (1)
    2. October (7)
    3. September (21)
    4. August (28)
    5. July (14)
    6. June (18)
    7. May (16)
    8. April (20)
    9. March (16)
    10. February (25)
    11. January (22)
  2. 2019 (255)
    1. December (21)
    2. November (25)
    3. October (16)
    4. September (20)
    5. August (18)
    6. July (12)
    7. June (23)
    8. May (23)
    9. April (32)
    10. March (25)
    11. February (16)
    12. January (24)
  3. 2018 (217)
  4. 2017 (36)
  5. 2016 (21)
  6. 2015 (36)
  7. 2014 (33)
  8. 2013 (23)
  9. 2012 (4)
  10. 2011 (1)
  11. 2010 (1)
  12. 2009 (1)
  13. 2008 (1)