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
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 
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 