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 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\).
|