Discrete Analysis Seminar

The Solovay--Kitaev theorem, which has important ramifications in quantum computing, gives guarantees on approximations of an arbitrary element of \(SU(2)\) using a fixed finite set, so long as that set generates a dense subgroup. Given element \(g\) and precision \(\varepsilon\), it was known how to compute in \(\textnormal{poly}\log(1/\varepsilon)\) time a \(\varepsilon\)-approximation which uses \(O(\log^{3.001}(1/\varepsilon))\)-many gates from the set. Kuperberg recently improved this count to \(O(\log^{1.45}(1/\varepsilon))\). We will discuss the proof of this new development.

Log-concave distributions over \(\mathbb{R}^n\) are distributions with density functions of the form \(e^V\) where \(V\) is a concave function over \(\mathbb{R}^n\). Such distributions demonstrate strong concentration properties and yet are broad enough to include distribution such as the Gaussian distribution, the Laplace distribution, and uniform measures on convex sets. In search of an analogous notion over the Boolean cube, Eldan and Shamir study \(\beta\)-semi-log-concave measures over the Booleaan cube, which are measures \(\nu\) over \(\{-1, 1\}^n\) whose multilinear extension \(f\) satisfies \(\nabla^2 \log f(x) \le \beta I_n\) for some \(\beta \ge 0\). They prove that any Hamming Lipschitz test function \(\varphi\) over \(\{-1, 1\}^n\) satisfies \(\mathrm{Var}_{\nu}[\varphi] \le n^{2 - C_\beta}\) for some \(C_\beta > 0\), which demonstrates a concentration of measure of \(\mu\). In this talk, we will present the proof of their result via stochastic localization.

Last week, we presented the martingale method for the uniform measure (more generally, product measures) over \(C_n \triangleq \{-1, 1\}^n\) that showed that \(\textnormal{Var}_{\nu}(\varphi) \le O(n)\) for any \(1\)-Hamming-Lipschitz function \(\varphi : C_n \to \mathbb{R}\). Then we realized that the martingale method holds for any localization process on \(\nu\). We ended with motivating stochastic localization as a continuous-time version of the martingale method. This week, we will show that stochastic localization on \(\nu\) is in fact a localization process, making it feasible to apply the martingale method over continuous-time. We will then reduce the problem down to showing that the rate of change of exponential tilts on \(\nu\) with respect to the Wasserstein distance is at most \(O(\beta n^{1 - c_\beta})\) for some \(c_\beta > 0\), which is the heart of the analysis and the part that crucially uses the \(\beta\)-semi-log-concavity of our measure \(\nu\).

Ising models are distributions on the Boolean hypercube which allow for nearest neighbor interactions; these models have a rich history throughout statistical physics and TCS. The Sherrington-Kirkpatrick (SK) ensemble is a restricted family of Ising models whose interaction matrices are iid Gaussians. A longstanding open problem in this area is to precisely nail down the temperature threshold for efficiently sampling from the SK model. El Alaoui, Montanari, and Sellke eschew the typical Markov chain approach for approximate sampling (in a total variation sense) and instead shoot for weaker Wasserstein sampling by simulating the stochastic localization SDE. The key idea is to use Approximate Message Passing (AMP) as a subroutine for accurately estimating the means of the intermediate tilted distributions in the localization process. With this approach, they are able to get within a constant factor of the conjectured temperature threshold for efficient sampling, and also prove a complementary hardness result for stable sampling algorithms above the conjectured threshold. In this talk we will contextualize their results and explain the main ideas behind their proofs.

When you want a sample from a high-temperature Ising model, you run the Glauber dynamics Markov chain until it is close to the stationary distribution. But how do you know when that happens? The cutoff phenomenon says that there is a particular time before which the Markov chain is far from stationary, and after which the Markov chain is close to stationary. In this talk we will discuss a proof of the cutoff phenomenon for this model, which uses a framework called Information Percolation to achieve quite precise results.

I'll talk about polynomial Markov chains, a non-linear generalization of Markov chains which arose in genetic algorithms and chemical reaction networks. For such dynamics with a certain stationary condition, even the convergence is an open problem. Under the added assumption of these dynamics being reversible/detailed balanced, where also convergence was open, I'll present a proof of convergence of such dynamics from any starting point away from the boundary. This settles the Global Attractor and Persistence Conjecture for Reversible Non-Linear Markov Chains.

Suppose we are attempting to construct an object which satisfies a given list of constraints. The Lovasz Local Lemma states that such an object will exist provided that (a) the constraints are not too dependent on each other and (b) each individual constraint is often satisfied. It turns out that a simple randomized algorithm will efficiently find a construction satisfying all the constraints. The analysis uses an interesting technique called entropy compression which this talk will describe.

In this talk we will discuss Asano's method, which can be used to prove Lee--Yang-type theorems concerning zero-free regions of partition functions for systems in statistical mechanics and thus correspond to an absence of phase transitions. Asano's method was first formulated in the quantum setting using special differential operators on a certain class of rational functions, but can be realized in the classical setting as a specific graph contraction. In the classical setting, we will discuss the ferromagnetic Ising model, and in the quantum setting we will discuss the Heisenberg XXZ model.

We will discuss Asano's method, which can be used to prove Lee-Yang-type theorems concerning zero-free regions of partition functions for systems in statistical mechanics and thus correspond to an absence of phase transitions. Asano's method was first formulated in the quantum setting using special differential operators on a certain class of rational functions, but can be realized in the classical setting as a specific graph contraction. In the classical setting, the subject of the first part of the talk, we discussed the ferromagnetic Ising model, and in the quantum setting this week we will discuss the Heisenberg XXZ model.

Sometimes we want to invert non-invertible matrices; for instance, we may wish to solve an overspecified system Ax=b, or compute the resolvent of a perturbed operator at a possible eigenvalue. The "Grushin problem method" suggests we augment the matrix by adding some rows and columns in a way that guarantees the resulting matrix is invertible. The inverse of this augmented matrix often encodes enough information about the original matrix to solve the problem at hand.