Discrete Analysis Seminar

This seminar is hosted weekly on Fridays 12:30 - 2pm Wednesdays 4 - 5:30pm. Contact if you would like to be added to the mailing list. It is a hybrid model with speakers remote on Zoom but an in-person viewing in Evans 748 Evans 740.

Zoom Link

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
Feb 4 Tarun Kathuria Matrix Concentration Inequalities and Free Probability arxiv
Feb 11 Tarun Kathuria Matrix Concentration Inequalities and Free Probability (part 2)
Feb 18 Jorge Vargas Strong convergence of random matrices from spectral inclusion of linear pencils
In this talk I will discuss one of the main pieces in the proof of Theorem 1.3 in [BBvH21], which is a statement about strong convergence of a general family \(H_1^N,\dots, H_k^N\) of Gaussian random matrices. In particular, this result implies that random matrices obtained by evaluating a non-commutative polynomial in the \(H_i^N\) do not have eigenvalue outliers, and gives some machinery to compute the edge of the bulk. This talk will be self-contained and its key ideas, which can be applied to other random matrix models, go back to a paper of Haagerup and Thorbjornsen from 2005. More specifically, the starting point of the talk will be a bound on the norm of the resolvant of linear pencils with matrix coefficients on the \(H_i^N\) which will be used as a black-box (this bound is proven in [BBvH21] using the interpolation technique that Tarun explained in the previous two talks), from where I will explain how to control quantities of the form \(\|p(H_1^N, \dots, H_k^N)\|\), where \(p\) is a non-commutative polynomial.
Feb 25 Sidhanth Mohanty Noise sensitivity of the top eigenvector of a random matrix
Suppose \(M\) is a random matrix and \(M'\) is a matrix we get after applying some noise, when is the top eigenvector of \(M'\) barely different from that of \(M\)? When is it completely uncorrelated? The behavior observed is a phase transition from near-perfect correlation to near-zero correlation as we increase the amount of noise, and the location of this phase transition is now understood for several random matrix models of interest. Notably, when \(M\) is a Wigner matrix, and \(M'\) is obtained by resampling \(k\) random entries of \(M\), the top eigenvectors of \(M\) and \(M'\) are closely aligned when \(k \ll n^{5/3-o(1)}\) and are near-orthogonal when \(k \gg n^{5/3}\). The goal of this talk is to go over a proof of this fact when M is a Gaussian matrix.
book arxiv 1 arxiv 2
March 4 Theo McKenzie Universality of nodal count distribution in large metric graphs
We examine the nodal count, namely the number of 0's, of eigenfunctions of quantum graphs. Alon, Band, and Berkolaiko conjecture that the normalized distribution of nodal counts for the first \(n\) eigenfunctions converges to the Gaussian distribution as n goes to infinity. We give their proof of this conjecture for certain limiting cases, and also give a method for computing these distributions efficiently.
March 11 Theo McKenzie Universality of nodal count distribution in large metric graph (part 2)
In the second part of my talk, we will prove that the nodal surplus is equal to the number of positive eigenvalues of the Hessian on the space of equipartitions. In order to define an equipartition, we examine properties of the zero set of eigenfunctions on quantum graphs. Finally, we will show how this Hessian can be calculated in the torus of phases introduced in the first part of the talk.
March 18 Elizabeth Yang Quantum Tanner Codes
To start, I'll first spend some time introducing the CSS code framework for quantum coding, and then describe the new "left-right Cayley complex" construction and how to obtain the rate and distance bounds for its corresponding quantum code. This new construction also has connections to the recent breakthrough of Dinur et al, in which they construct the first known \(c^3\) locally testable codes. Similar ideas can be used both to prove linearly growing minimum distance for the quantum code, and to prove local testability for Dinur et al's classical code.
arxiv (no video)
March 25 Spring Break!
April 1 Elizabeth Yang Quantum Tanner Codes (part 2)
This week, we'll dive into the actual construction of quantum Tanner codes by Leverrier and Zemor, based on the square Cayley complex of Dinur et al. The main technical challenge we will tackle is understanding the quantum distance of these quantum Tanner codes.
April 6 Omar Alrabiah Quantum Tanner Codes (part 3)
In this talk, we are going to wrap up the series on the Quantum Tanner Codes of (Leverrier and Zemor, 2022) by showing their quantum distance lower bound. First, we will prove the robustness proposition stated in the last talk. After that, we are going to show the distance lower bound for the Expander Codes of (Sipser and Spielman, 1996) as a warm-up toward the quantum distance lower bound. Finally, we will end by proving the quantum distance lower bound.
April 13 Omar Alrabiah Quantum Tanner Codes (part 4)
Final part in this series, see part 3 for abstract.
April 20 Rikhav Shah Worst case to average case reduction for matrix multiplication
Say one is given a defective oracle for multiplying matrices over some finite field \(\mathbb{F}\). Specifically, say that it only outputs the correct value of \(AB\) for just 1% of possible pairs of matrices \(A,B\). Can the oracle be repaired? The answer is yes: the oracle can be efficiently turned into a randomized algorithm which computes \(AB\) in all cases with probability 99%.
April 27 Zach Stier Short paths in LPS graphs and \(PU(2)\)
Carvalho Pinto and Petit recently devised a method for efficiently computing paths of length \(\frac{7}{3}\log_pq\) in the LPS Ramanujan graph \(X^{p,q}\). This approach to the problem in a discrete setting has adaptations to continuous settings such as quantum hardware design, where the path length grows as \(\frac{7}{3}\log_{59}\frac{1}{\varepsilon^3}\) for precision $\varepsilon$. In this talk we will cover these algorithms for factorizations in LPS graphs and \(PU(2)\) (single-qubit gates, via golden gates), and time permitting discuss additional number-theoretic aspects of these constructions.
paper 1 paper 2 arxiv