Friday, September 16, 2022

Friday, September 16, 2022 — 1:00 PM EDT

Title: Stochastic Probing with Applications

Speaker: David Kalichman Affiliation: University of Waterloo Location: MC 6029 or contact Rian Neogi for Zoom link

Abstract:  We will explore a stochastic probing problem. Given a set of elements which have weights and independent probabilities of being "active," the goal is to construct a subset of active elements of maximum weight. To form such a set, we must "probe" elements sequentially to determine whether they are active.

Friday, September 16, 2022 — 3:30 PM EDT

Title: Cheeger Inequalities for Vertex Expansion and Reweighted Eigenvalues

Speaker: Lap Chi Lau Affiliation: University of Waterloo Location: MC 5501

Abstract:

The classical Cheeger's inequality relates the edge conductance $\phi$ of a graph and the second smallest eigenvalue $\lambda_2$ of the Laplacian matrix. Recently, Olesker-Taylor and Zanetti discovered a Cheeger-type inequality $\psi^2 / \log |V| \lesssim \lambda_2^* \lesssim \psi$ connecting the vertex expansion $\psi$ of a graph $G=(V,E)$ and the maximum reweighted second smallest eigenvalue $\lambda_2^*$ of the Laplacian matrix. In this work, we first improve their result to $\psi^2 / \log d \lesssim \lambda_2^* \lesssim \psi$ where $d$ is the maximum degree in $G$, which is optimal assuming the small-set expansion conjecture. Also, the improved result holds for weighted vertex expansion, answering an open question by Olesker-Taylor and Zanetti. 

S M T W T F S
28
29
30
31
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
1
  1. 2022 (144)
    1. December (2)
    2. November (18)
    3. October (15)
    4. September (11)
    5. August (2)
    6. July (17)
    7. June (17)
    8. May (10)
    9. April (12)
    10. March (18)
    11. February (10)
    12. January (13)
  2. 2021 (103)
    1. December (3)
    2. November (7)
    3. October (6)
    4. September (12)
    5. August (6)
    6. July (10)
    7. June (12)
    8. May (7)
    9. April (9)
    10. March (13)
    11. February (8)
    12. January (10)
  3. 2020 (119)
  4. 2019 (167)
  5. 2018 (136)
  6. 2017 (103)
  7. 2016 (137)
  8. 2015 (136)
  9. 2014 (88)
  10. 2013 (48)
  11. 2012 (39)
  12. 2011 (36)
  13. 2010 (40)
  14. 2009 (40)
  15. 2008 (39)
  16. 2007 (15)