[Theory] 11/7 Young Researcher Seminar Series: June Vuong, Stanford

[Mary Marre]

*(PLEASE NOTE SPECIAL TIME!)*

*When:*        Monday, November 7th at *3 **pm CT   *


*Where:       *Talk will be given *live, in-person* at

                   TTIC, 6045 S. Kenwood Avenue

                   5th Floor, Room 530


*Virtually:*  via Panopto (*livestream*
<https://uchicago.hosted.panopto.com/Panopto/Pages/Viewer.aspx?id=72b5485e-fb43-4971-9a37-af3f0167d327>
)


*Who: *        June Vuong, Stanford University


------------------------------

*Title:* Optimal Sublinear Sampling of Spanning Trees and Determinantal
Point Processes via Average-Case Entropic Independence
*Abstract: *We design fast algorithms for repeatedly sampling from strongly
Rayleigh distributions, which include as special cases random spanning tree
distributions and determinantal point processes. For a graph G=(V, E), we
show how to approximately sample uniformly random spanning trees from G in
$O(| V | log ^2 |V|) time per sample after an initial $O(|E| polylog |E|)$
time preprocessing. This is the first nearly-linear runtime in the output
size, which is clearly optimal. For a determinantal point process on
k-sized subsets of a ground set of n elements, defined via an nxn kernel
matrix, we show how to approximately sample in $\tilde{O}(k^\omega)$ time
after an initial $\tilde{O}(nk^{\omega-1})$ time preprocessing, where
$\omega<2.372864$ is the matrix multiplication exponent. The time to
compute just the weight of the output set is roughly $k^\omega$, a natural
barrier that suggests our runtime might be optimal for determinantal point
processes as well. As a corollary, we even improve the state of the art for
obtaining a single sample from a determinantal point process, from the
prior runtime of $\tilde{O}(\min\{nk^2, n^\omega\})$ to
$\tilde{O}(nk^{\omega-1})$.

In our main technical result, we achieve the optimal limit on domain
sparsification for strongly Rayleigh distributions. In domain
sparsification, sampling from a distribution $\mu$ on $\binom{[n]}{k}$ is
reduced to sampling from related distributions on $\binom{[t]}{k}$ for $t
\leq n$. We show that for strongly Rayleigh distributions, the domain size
can be reduced to nearly linear in the output size $t=\tilde{O}(k)$,
improving the state of the art from $t= \tilde{O}(k^2)$ for general
strongly Rayleigh distributions and the more specialized
$t=\tilde{O}(k^{1.5})$ for spanning tree distributions. Our reduction
involves sampling from $\tilde{O}(1)$ domain-sparsified distributions, all
of which can be produced efficiently assuming approximate overestimates for
marginals of $\mu$ are known and stored in a convenient data structure.
Having access to marginals is the discrete analog of having access to the
mean and covariance of a continuous distribution, or equivalently knowing
``isotropy'' for the distribution, the key behind optimal samplers in the
continuous setting based on the famous Kannan-Lov\'asz-Simonovits (KLS)
conjecture. We view our result as analogous in spirit to the KLS conjecture
and its consequences for sampling, but rather for discrete strongly
Rayleigh measures.
Joint work with Nima Anari and Yang P. Liu. To appear in FOCS 2022.
Arxiv link [2204.02570v1] Optimal Sublinear Sampling of Spanning Trees and
Determinantal Point Processes via Average-Case Entropic Independence
(arxiv.org) <https://arxiv.org/abs/2204.02570v1>


*Host: Madhur Tulsiani <madhurt at ttic.edu>*

**************************************************************************************************



The *TTIC Young Researcher Seminar Series* (http://www.ttic.edu/young-
researcher.php) features talks by Ph.D. students and postdocs
whose research is of broad interest to the computer science community. The
series provides an opportunity for early-career researchers to present
recent work to and meet with students and faculty at TTIC and nearby
universities.


The seminars are typically held on Wednesdays at 10:30am in TTIC Room 530.

For additional information, please contact *David McAllester *(
mcallester at ttic.edu).









]

Mary C. Marre
Faculty Administrative Support
*Toyota Technological Institute*
*6045 S. Kenwood Avenue*
*Chicago, IL  60637*
*mmarre at ttic.edu <mmarre at ttic.edu>*
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mailman.cs.uchicago.edu/pipermail/theory/attachments/20221031/3da24527/attachment.html>