This seminar is hosted weekly on Fridays 12:30  2pm. Contact if you would like to be added to the mailing list. It will be held inperson in Evans 891.
Date  Presenter  Topic (hover for abstract)  Links 

Sept 2  Sidhanth Mohanty 
Localization schemes for mixing of Markov chains
The simple random walk on the \(n\)dimensional hypercube mixes to the
uniform distribution once every coordinate is touched at least once, which
happens in \(O(n \log n)\) time. However, analyzing mixing times of random
walks for sampling from distributions on the hypercube even with mild
correlations across coordinates is a lot trickier. In recent years,
techniques based on highdimensional expansion have been successful in
analyzing such random walks in the context of sampling bases in a matroid,
independent sets and colorings in graphs, and the Gibbs distributions of
various Ising models. We will discuss this paper of Chen and Eldan, which
presents a clean generalization of the highdimensional expansion framework,
and establishes "localtoglobal" theorems for objects beyond simplicial
complexes. In particular, we will go over their framework, a proof of their
localtoglobal theorem, and some examples.

arxiv 
Sept 9  Siqi Liu 
Localization schemes for mixing of Markov chains
This is a continuation of last week's talk.

arxiv 
Sept 16  Edward Zeng 
Sparse smoothed analysis
The condition number \(\kappa(M) = \M\\M^{1}\\) of a matrix \(M\) is
important in numerical linear algebra. Under mild assumptions, Tao and Vu
proved that \(\kappa(M)\) can be regularized (i.e., made to be only
polynomially large) by adding a random sparse matrix. I will go over
their proof.

arxiv (see Theorem 2.9) 
Sept 23  Edward Zeng 
Sparse smoothed analysis (pt 2)
This is a continuation of last week's talk.


Sept 30  Zack Stier 
Quantum ergodicity for regular graphs
Quantum ergodicity states that eigenfunctions for a regular graph are
delocalized in that the average of any vertex function under the probability
distribution from an eigenfunction is typically near the function's uniform
average. It was initially proved by Anantharaman and Le Masson, and
Anantharaman later gave three additional proofs. We will discuss one of
those subsequent proofs.

paper notes 
Oct 7  Joao Basso 
Towards a quantum algorithm for the Unique Sink Orientation problem
If a directed hypercube satisfies the property that every subface has a
unique sink (a node with only incoming edges), then it is called a unique
sink orientation (USO). Given a USO, being able to find the global sink
efficiently would imply efficient algorithms for many problems in
optimization, linear programming and the theory of games. While there are no
known polynomialtime classical algorithms for this problem, Bacon showed
that there is an efficient quantum algorithm if one is able to solve a
selfcontained discrete math problem. After a brief overview of quantum
algorithms and the structure of USOs, we will go over the missing piece and
the implied quantum algorithm.

arxiv 
Oct 14  Izzy Detherage 
Improved Cheeger's Inequality
A wellknown result in spectral graph theory is Cheeger's inequality, which
gives bounds on the conductance of a graph in terms of the first nontrivial
eigenvalue of the normalized Laplacian. To prove the upper bound of
Cheeger's inequality, we consider spectral partitions, a partition of
the vertices based on the first nontrivial eigenvector. Kwok et. al.
improve on Cheeger's inequality by showing such spectral partitions satisfy
an upper bound dependent on higher order spectral gaps. Kwok et. al. provide
two proofs of their theorem; we will give a brief overview of Cheeger's
inequality, then discuss the first proof in detail and the general idea of
the second.

arxiv 
Oct 21  Vilas Winstein 
Critical Random Graphs and Brownian Excursions
The ErdősRényi model of random graphs exhibits a phase transition in which
a giant component emerges. At criticality, there are many big (but not
giant) components. The sizes of these components can be described, in the
limit, by a random process which at first seems entirely unrelated: the
sequence of excursions of a reflected drifting brownian motion. We will
explore this connection and provide some intuition for the proof.

paper 
Oct 28  Vilas Winstein 
Critical Random Graphs and Brownian Excursions (pt 2)
This time, we will go through the details of the proof.

notes 
Nov 4  Rikhav Shah 
Is a graph a manifold?
No, obviously. But making an analogy between graphs and manifolds turns out
to be surprisingly fruitful. In particular, we can define a few notions of
“curvature” of a graph that posses some of the nice qualities of the
curvature of a Riemannian manifold. We will discuss the relationship between
the curvature of a graph and various combinatorial properties, like it's
diameter mixing time, cutoff, and expansion.
