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.
Date  Presenter  Topic (hover for abstract)  Links 

September 7  Zack Stier 
Recent improvements on the SolovayKitaev
theorem
The SolovayKitaev 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
Logconcave 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\)semilogconcave 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\)HammingLipschitz 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
continuoustime 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
continuoustime. 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\)semilogconcavity of
our measure \(\nu\).
