Discrete Analysis Seminar

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 in-person in Evans 891.

Zoom Link

Each week we'll announce to the mailing list if the talk will streamed on zoom. The zoom link is hidden unless you've been given the password or the special link.

Schedule (Spring 2022)

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 high-dimensional 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 high-dimensional expansion framework, and establishes "local-to-global" theorems for objects beyond simplicial complexes. In particular, we will go over their framework, a proof of their local-to-global 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 polynomial-time classical algorithms for this problem, Bacon showed that there is an efficient quantum algorithm if one is able to solve a self-contained 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