Discrete Analysis Seminar

This seminar is hosted weekly on Thursdays 12:30 - 2pm in Evans 732. We meet for lunch just outside Evans at 11:30 before the seminar each week. Contact if you would like to be added to the mailing list.

Schedule (Fall 2023)

Date Presenter Topic (hover for abstract) Links
September 7 Zack Stier Recent improvements on the Solovay--Kitaev theorem
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.
arxiv
September 14 Omar Alrabiah A notion of log concavity on the Boolean cube
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.
arxiv
September 21 Omar Alrabiah A notion of log concavity on the Boolean cube (part 2)
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\).