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

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 (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 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
Oct 14 Izzy Detherage Improved Cheeger's Inequality
A well-known result in spectral graph theory is Cheeger's inequality, which gives bounds on the conductance of a graph in terms of the first non-trivial 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 non-trivial 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ős-Ré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.