<div dir="ltr"><div dir="ltr"><div class="gmail_default" style="font-size:small"><div dir="ltr"><div style="font-family:arial,helvetica,sans-serif;font-size:12.8px"><font style="font-size:small;color:rgb(0,0,0);font-family:arial,sans-serif;vertical-align:inherit"><font style="vertical-align:inherit"><b style="color:rgb(34,34,34);background-color:rgb(255,255,0)"><font color="#000000">(</font><i style="color:rgb(0,0,0)">PLEASE NOTE SPECIAL TIME!)</i></b><b><br></b></font></font></div><div style="font-family:arial,helvetica,sans-serif;font-size:12.8px"><font style="font-size:small;color:rgb(0,0,0);font-family:arial,sans-serif;vertical-align:inherit"><font style="vertical-align:inherit"><b style="color:rgb(34,34,34);background-color:rgb(255,255,0)"><i style="color:rgb(0,0,0)"><br></i></b></font></font></div><div style="font-size:12.8px"><font style="font-family:arial,sans-serif;font-size:small;color:rgb(0,0,0);vertical-align:inherit"><font style="vertical-align:inherit"><b>When:</b>    </font></font><font style="font-size:small;vertical-align:inherit"><font style="vertical-align:inherit"><font style="color:rgb(0,0,0)">    Monday</font><span class="gmail_default" style="font-family:arial,sans-serif;color:rgb(0,0,0)">, November 7th</span><font style="color:rgb(0,0,0)"> at</font><b style="color:rgb(0,0,0)"> </b><b style="background-color:rgb(255,255,0)"><u><font color="#0000ff" face="verdana, sans-serif">3 </font></u></b><font face="verdana, sans-serif"><b style="background-color:rgb(255,255,0)"><u><font color="#0000ff">pm CT</font></u><font color="#000000">   </font></b></font></font></font><br></div></div><div><p style="color:rgb(80,0,80);font-variant-numeric:normal;font-variant-east-asian:normal;font-stretch:normal;line-height:normal;margin:0px"><font face="arial, sans-serif" color="#000000"><font style="vertical-align:inherit"><font style="vertical-align:inherit"><b><span style="background-color:rgb(255,255,0)"><br></span></b></font></font></font></p><div class="gmail_default"><font face="arial, sans-serif"><b><font color="#500050">Where:      </font><font color="#000000"> </font></b><font color="#000000">Talk will be given </font><font color="#0000ff" style="font-weight:bold"><u>live, in-person</u></font><font style="color:rgb(80,0,80);font-weight:bold"> </font><font style="color:rgb(80,0,80)">at</font></font></div><p class="MsoNormal" style="margin:0in;line-height:normal;background-image:initial;background-position:initial;background-size:initial;background-repeat:initial;background-origin:initial;background-clip:initial"><font face="arial, sans-serif"><font color="#500050">               </font><font color="#000000">    TTIC, 6045 S. Kenwood Avenue</font></font></p><p class="MsoNormal" style="margin:0in;line-height:normal;background-image:initial;background-position:initial;background-size:initial;background-repeat:initial;background-origin:initial;background-clip:initial"><font face="arial, sans-serif" color="#000000">                   5th Floor, Room 530<b> </b></font></p><p class="MsoNormal" style="margin:0in;color:rgb(80,0,80);line-height:normal;background-image:initial;background-position:initial;background-size:initial;background-repeat:initial;background-origin:initial;background-clip:initial"><font face="arial, sans-serif"><b><span style="color:black"><br></span></b></font></p><p class="MsoNormal" style="margin:0in 0in 0.0001pt;line-height:normal;background-image:initial;background-position:initial;background-size:initial;background-repeat:initial;background-origin:initial;background-clip:initial"><b style="color:rgb(60,64,67);font-family:Roboto,Arial,sans-serif;letter-spacing:0.2px;white-space:pre-wrap">Virtually:</b><span style="font-size:14px;color:rgb(60,64,67);font-family:Roboto,Arial,sans-serif;letter-spacing:0.2px;white-space:pre-wrap">    via Panopto </span><a href="https://uchicago.hosted.panopto.com/Panopto/Pages/Viewer.aspx?id=72b5485e-fb43-4971-9a37-af3f0167d327" target="_blank" style="color:rgb(26,115,232);font-size:14px;font-family:Roboto,Arial,sans-serif;letter-spacing:0.2px;white-space:pre-wrap">(<b>livestream</b></a><span style="font-size:14px;color:rgb(60,64,67);font-family:Roboto,Arial,sans-serif;letter-spacing:0.2px;white-space:pre-wrap">)</span><br></p><p class="MsoNormal" style="margin:0in 0in 0.0001pt;color:rgb(80,0,80);line-height:normal;background-image:initial;background-position:initial;background-size:initial;background-repeat:initial;background-origin:initial;background-clip:initial"><font face="arial, sans-serif"><br></font></p><p class="MsoNormal" style="margin:0in 0in 0.0001pt;line-height:normal;background-image:initial;background-position:initial;background-size:initial;background-repeat:initial;background-origin:initial;background-clip:initial"><font face="arial, sans-serif"><font style="vertical-align:inherit"><font style="vertical-align:inherit"><font style="color:rgb(80,0,80)"><b>Who: </b> </font><font color="#500050" style="color:rgb(80,0,80)">    </font><font color="#000000"><font color="#500050">   </font></font></font></font></font>June Vuong, Stanford University</p><p class="MsoNormal" style="margin:0in 0in 0.0001pt;color:rgb(80,0,80);line-height:normal;background-image:initial;background-position:initial;background-size:initial;background-repeat:initial;background-origin:initial;background-clip:initial"><br></p><div class="MsoNormal" align="center" style="margin:0in 0in 8pt;font-size:11pt;text-align:center;line-height:15.6933px;font-family:Calibri,sans-serif"><hr size="2" width="100%" align="center"></div><div><p style="color:rgb(60,64,67);letter-spacing:0.2px;white-space:pre-wrap"><font face="arial, sans-serif"><span style="color:black;letter-spacing:normal"><b>Title:</b> Optimal Sublinear Sampling of Spanning Trees and Determinantal Point Processes via Average-Case Entropic Independence</span></font></p><div style="color:black;margin:0px"><font face="arial, sans-serif"><b>Abstract: </b>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})$.</font><div style="margin:0px"><font face="arial, sans-serif">            </font></div><font face="arial, sans-serif">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.</font></div><div style="color:black;margin:0px"><font face="arial, sans-serif">Joint work with Nima Anari and Yang P. Liu. To appear in FOCS 2022.</font></div><div style="color:black;margin:0px"><span style="font-family:arial,sans-serif">Arxiv link </span><a href="https://arxiv.org/abs/2204.02570v1" rel="noopener noreferrer" target="_blank" style="font-family:arial,sans-serif;margin:0px">[2204.02570v1] Optimal Sublinear Sampling of Spanning Trees and Determinantal Point Processes via Average-Case Entropic Independence (arxiv.org)</a><br></div><div dir="ltr"><span style="color:rgb(80,0,80)"><font face="arial, sans-serif"><div><br></div><div><br></div></font></span></div><b>Host: <a href="mailto:madhurt@ttic.edu" target="_blank">Madhur Tulsiani</a></b></div><div><br></div></div><div><div style="font-size:12.8px"><font face="arial, helvetica, sans-serif">**************************************************************************************************<br></font></div><div style="font-size:12.8px"><div><p class="MsoNormal" style="margin-bottom:0.0001pt;font-family:arial,sans-serif"><font face="arial, helvetica, sans-serif"> </font></p><p class="MsoNormal" style="margin-bottom:0.0001pt;font-family:arial,sans-serif"><font face="arial, helvetica, sans-serif">The <font color="#3d85c6"><i><b>TTIC Young Researcher Seminar Series</b></i></font> (<a href="http://www.ttic.edu/young-researcher.php" target="_blank">http://www.ttic.edu/young-researcher.php</a>) 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.</font></p><p class="MsoNormal" style="margin-bottom:0.0001pt;font-family:arial,sans-serif"><font face="arial, helvetica, sans-serif"><br>The seminars are typically held on Wednesdays at 10:30am in TTIC Room 530.<br><br>For additional information, please contact <i>David McAllester </i>(<a href="mailto:mcallester@ttic.edu" target="_blank">mcallester@ttic.edu</a>).</font></p><p class="MsoNormal" style="margin-bottom:0.0001pt;font-family:arial,sans-serif"><font face="arial, helvetica, sans-serif"><br></font></p><p class="MsoNormal" style="margin-bottom:0.0001pt;font-family:arial,sans-serif"><font face="arial, helvetica, sans-serif"><br></font></p><p class="MsoNormal" style="margin-bottom:0.0001pt;font-family:arial,sans-serif"><font face="arial, helvetica, sans-serif"><br></font></p><p class="MsoNormal" style="margin-bottom:0.0001pt;font-family:arial,sans-serif"><font face="arial, helvetica, sans-serif"><br></font></p><p class="MsoNormal" style="margin-bottom:0.0001pt;font-family:arial,sans-serif"><font face="arial, helvetica, sans-serif"><br></font></p></div></div></div></div><div><div dir="ltr" class="gmail_signature"><div dir="ltr"><div><span style="font-family:arial,helvetica,sans-serif;font-size:x-small">Mary C. Marre</span><br></div><div><div><font face="arial, helvetica, sans-serif" size="1">Faculty Administrative Support</font></div><div><i><font face="arial, helvetica, sans-serif" color="#3d85c6" size="1"><b>Toyota Technological Institute</b></font></i></div><div><i><font face="arial, helvetica, sans-serif" color="#3d85c6" size="1">6045 S. Kenwood Avenue</font></i></div><div><font size="1"><i><font face="arial, helvetica, sans-serif" color="#3d85c6">Chicago, IL  60637</font></i><br></font></div><div><b><i><a href="mailto:mmarre@ttic.edu" target="_blank"><font face="arial, helvetica, sans-serif" size="1">mmarre@ttic.edu</font></a></i></b></div></div></div></div></div><br></div><br><div class="gmail_quote"><div dir="ltr" class="gmail_attr">On Mon, Nov 7, 2022 at 1:51 PM Mary Marre <<a href="mailto:mmarre@ttic.edu">mmarre@ttic.edu</a>> wrote:<br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><div dir="ltr"><div dir="ltr"><div style="font-size:small"><div dir="ltr"><div style="font-family:arial,helvetica,sans-serif;font-size:12.8px"><font style="font-size:small;color:rgb(0,0,0);font-family:arial,sans-serif;vertical-align:inherit"><font style="vertical-align:inherit"><b style="color:rgb(34,34,34);background-color:rgb(255,255,0)"><font color="#000000">(</font><i style="color:rgb(0,0,0)">PLEASE NOTE SPECIAL TIME!)</i></b><b><br></b></font></font></div><div style="font-family:arial,helvetica,sans-serif;font-size:12.8px"><font style="font-size:small;color:rgb(0,0,0);font-family:arial,sans-serif;vertical-align:inherit"><font style="vertical-align:inherit"><b style="color:rgb(34,34,34);background-color:rgb(255,255,0)"><i style="color:rgb(0,0,0)"><br></i></b></font></font></div><div style="font-size:12.8px"><font style="font-family:arial,sans-serif;font-size:small;color:rgb(0,0,0);vertical-align:inherit"><font style="vertical-align:inherit"><b>When:</b>    </font></font><font style="font-size:small;vertical-align:inherit"><font style="vertical-align:inherit"><font style="color:rgb(0,0,0)">    Monday</font><span class="gmail_default" style="font-family:arial,sans-serif;color:rgb(0,0,0)">, November 7th</span><font style="color:rgb(0,0,0)"> at</font><b style="color:rgb(0,0,0)"> </b><b style="background-color:rgb(255,255,0)"><u><font color="#0000ff" face="verdana, sans-serif">3 </font></u></b><font face="verdana, sans-serif"><b style="background-color:rgb(255,255,0)"><u><font color="#0000ff">pm CT</font></u><font color="#000000">   </font></b></font></font></font><br></div></div><div><p style="color:rgb(80,0,80);font-variant-numeric:normal;font-variant-east-asian:normal;font-stretch:normal;line-height:normal;margin:0px"><font face="arial, sans-serif" color="#000000"><font style="vertical-align:inherit"><font style="vertical-align:inherit"><b><span style="background-color:rgb(255,255,0)"><br></span></b></font></font></font></p><div><font face="arial, sans-serif"><b><font color="#500050">Where:      </font><font color="#000000"> </font></b><font color="#000000">Talk will be given </font><font color="#0000ff" style="font-weight:bold"><u>live, in-person</u></font><font style="color:rgb(80,0,80);font-weight:bold"> </font><font style="color:rgb(80,0,80)">at</font></font></div><p class="MsoNormal" style="margin:0in;line-height:normal;background-image:initial;background-position:initial;background-size:initial;background-repeat:initial;background-origin:initial;background-clip:initial"><font face="arial, sans-serif"><font color="#500050">               </font><font color="#000000">    TTIC, 6045 S. Kenwood Avenue</font></font></p><p class="MsoNormal" style="margin:0in;line-height:normal;background-image:initial;background-position:initial;background-size:initial;background-repeat:initial;background-origin:initial;background-clip:initial"><font face="arial, sans-serif" color="#000000">                   5th Floor, Room 530<b> </b></font></p><p class="MsoNormal" style="margin:0in;color:rgb(80,0,80);line-height:normal;background-image:initial;background-position:initial;background-size:initial;background-repeat:initial;background-origin:initial;background-clip:initial"><font face="arial, sans-serif"><b><span style="color:black"><br></span></b></font></p><p class="MsoNormal" style="margin:0in 0in 0.0001pt;line-height:normal;background-image:initial;background-position:initial;background-size:initial;background-repeat:initial;background-origin:initial;background-clip:initial"><b style="color:rgb(60,64,67);font-family:Roboto,Arial,sans-serif;letter-spacing:0.2px;white-space:pre-wrap">Virtually:</b><span style="font-size:14px;color:rgb(60,64,67);font-family:Roboto,Arial,sans-serif;letter-spacing:0.2px;white-space:pre-wrap">    via Panopto </span><a href="https://uchicago.hosted.panopto.com/Panopto/Pages/Viewer.aspx?id=72b5485e-fb43-4971-9a37-af3f0167d327" style="color:rgb(26,115,232);font-size:14px;font-family:Roboto,Arial,sans-serif;letter-spacing:0.2px;white-space:pre-wrap" target="_blank">(<b>livestream</b></a><span style="font-size:14px;color:rgb(60,64,67);font-family:Roboto,Arial,sans-serif;letter-spacing:0.2px;white-space:pre-wrap">)</span><br></p><p class="MsoNormal" style="margin:0in 0in 0.0001pt;color:rgb(80,0,80);line-height:normal;background-image:initial;background-position:initial;background-size:initial;background-repeat:initial;background-origin:initial;background-clip:initial"><font face="arial, sans-serif"><br></font></p><p class="MsoNormal" style="margin:0in 0in 0.0001pt;line-height:normal;background-image:initial;background-position:initial;background-size:initial;background-repeat:initial;background-origin:initial;background-clip:initial"><font face="arial, sans-serif"><font style="vertical-align:inherit"><font style="vertical-align:inherit"><font style="color:rgb(80,0,80)"><b>Who: </b> </font><font color="#500050" style="color:rgb(80,0,80)">    </font><font color="#000000"><font color="#500050">   </font></font></font></font></font>June Vuong, Stanford University</p><p class="MsoNormal" style="margin:0in 0in 0.0001pt;color:rgb(80,0,80);line-height:normal;background-image:initial;background-position:initial;background-size:initial;background-repeat:initial;background-origin:initial;background-clip:initial"><br></p><div class="MsoNormal" align="center" style="margin:0in 0in 8pt;font-size:11pt;text-align:center;line-height:15.6933px;font-family:Calibri,sans-serif"><hr size="2" width="100%" align="center"></div><div><p style="color:rgb(60,64,67);letter-spacing:0.2px;white-space:pre-wrap"><font face="arial, sans-serif"><span style="color:black;letter-spacing:normal"><b>Title:</b> Optimal Sublinear Sampling of Spanning Trees and Determinantal Point Processes via Average-Case Entropic Independence</span></font></p><div style="color:black;margin:0px"><font face="arial, sans-serif"><b>Abstract: </b>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})$.</font><div style="margin:0px"><font face="arial, sans-serif">            </font></div><font face="arial, sans-serif">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.</font></div><div style="color:black;margin:0px"><font face="arial, sans-serif">Joint work with Nima Anari and Yang P. Liu. To appear in FOCS 2022.</font></div><div style="color:black;margin:0px"><span style="font-family:arial,sans-serif">Arxiv link </span><a href="https://arxiv.org/abs/2204.02570v1" rel="noopener noreferrer" style="font-family:arial,sans-serif;margin:0px" target="_blank">[2204.02570v1] Optimal Sublinear Sampling of Spanning Trees and Determinantal Point Processes via Average-Case Entropic Independence (arxiv.org)</a><br></div><div dir="ltr"><span style="color:rgb(80,0,80)"><font face="arial, sans-serif"><div><br></div><div><br></div></font></span></div><b>Host: <a href="mailto:madhurt@ttic.edu" target="_blank">Madhur Tulsiani</a></b></div><div><br></div></div><div><div style="font-size:12.8px"><font face="arial, helvetica, sans-serif">**************************************************************************************************<br></font></div><div style="font-size:12.8px"><div><p class="MsoNormal" style="margin-bottom:0.0001pt;font-family:arial,sans-serif"><font face="arial, helvetica, sans-serif"> </font></p><p class="MsoNormal" style="margin-bottom:0.0001pt;font-family:arial,sans-serif"><font face="arial, helvetica, sans-serif">The <font color="#3d85c6"><i><b>TTIC Young Researcher Seminar Series</b></i></font> (<a href="http://www.ttic.edu/young-researcher.php" target="_blank">http://www.ttic.edu/young-researcher.php</a>) 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.</font></p><p class="MsoNormal" style="margin-bottom:0.0001pt;font-family:arial,sans-serif"><font face="arial, helvetica, sans-serif"><br>The seminars are typically held on Wednesdays at 10:30am in TTIC Room 530.<br><br>For additional information, please contact <i>David McAllester </i>(<a href="mailto:mcallester@ttic.edu" target="_blank">mcallester@ttic.edu</a>).</font></p></div></div></div></div><div><div dir="ltr"><div dir="ltr"><div><span style="font-family:arial,helvetica,sans-serif;font-size:x-small">Mary C. Marre</span><br></div><div><div><font face="arial, helvetica, sans-serif" size="1">Faculty Administrative Support</font></div><div><i><font face="arial, helvetica, sans-serif" color="#3d85c6" size="1"><b>Toyota Technological Institute</b></font></i></div><div><i><font face="arial, helvetica, sans-serif" color="#3d85c6" size="1">6045 S. Kenwood Avenue</font></i></div><div><font size="1"><i><font face="arial, helvetica, sans-serif" color="#3d85c6">Chicago, IL  60637</font></i><br></font></div><div><b><i><a href="mailto:mmarre@ttic.edu" target="_blank"><font face="arial, helvetica, sans-serif" size="1">mmarre@ttic.edu</font></a></i></b></div></div></div></div></div><br></div><br><div class="gmail_quote"><div dir="ltr" class="gmail_attr">On Sun, Nov 6, 2022 at 3:23 PM Mary Marre <<a href="mailto:mmarre@ttic.edu" target="_blank">mmarre@ttic.edu</a>> wrote:<br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><div dir="ltr"><div dir="ltr"><div style="font-size:small"><div dir="ltr"><div style="font-family:arial,helvetica,sans-serif;font-size:12.8px"><font style="font-size:small;color:rgb(0,0,0);font-family:arial,sans-serif;vertical-align:inherit"><font style="vertical-align:inherit"><b style="color:rgb(34,34,34);background-color:rgb(255,255,0)"><font color="#000000">(</font><i style="color:rgb(0,0,0)">PLEASE NOTE SPECIAL TIME!)</i></b><b><br></b></font></font></div><div style="font-family:arial,helvetica,sans-serif;font-size:12.8px"><font style="font-size:small;color:rgb(0,0,0);font-family:arial,sans-serif;vertical-align:inherit"><font style="vertical-align:inherit"><b style="color:rgb(34,34,34);background-color:rgb(255,255,0)"><i style="color:rgb(0,0,0)"><br></i></b></font></font></div><div style="font-size:12.8px"><font style="font-family:arial,sans-serif;font-size:small;color:rgb(0,0,0);vertical-align:inherit"><font style="vertical-align:inherit"><b>When:</b>    </font></font><font style="font-size:small;vertical-align:inherit"><font style="vertical-align:inherit"><font style="color:rgb(0,0,0)">    Monday</font><span class="gmail_default" style="font-family:arial,sans-serif;color:rgb(0,0,0)">, November 7th</span><font style="color:rgb(0,0,0)"> at</font><b style="color:rgb(0,0,0)"> </b><b style="background-color:rgb(255,255,0)"><u><font color="#0000ff" face="verdana, sans-serif">3 </font></u></b><font face="verdana, sans-serif"><b style="background-color:rgb(255,255,0)"><u><font color="#0000ff">pm CT</font></u><font color="#000000">   </font></b></font></font></font><br></div></div><div><p style="color:rgb(80,0,80);font-variant-numeric:normal;font-variant-east-asian:normal;font-stretch:normal;line-height:normal;margin:0px"><font face="arial, sans-serif" color="#000000"><font style="vertical-align:inherit"><font style="vertical-align:inherit"><b><span style="background-color:rgb(255,255,0)"><br></span></b></font></font></font></p><div><font face="arial, sans-serif"><b><font color="#500050">Where:      </font><font color="#000000"> </font></b><font color="#000000">Talk will be given </font><font color="#0000ff" style="font-weight:bold"><u>live, in-person</u></font><font style="color:rgb(80,0,80);font-weight:bold"> </font><font style="color:rgb(80,0,80)">at</font></font></div><p class="MsoNormal" style="margin:0in;line-height:normal;background-image:initial;background-position:initial;background-size:initial;background-repeat:initial;background-origin:initial;background-clip:initial"><font face="arial, sans-serif"><font color="#500050">               </font><font color="#000000">    TTIC, 6045 S. Kenwood Avenue</font></font></p><p class="MsoNormal" style="margin:0in;line-height:normal;background-image:initial;background-position:initial;background-size:initial;background-repeat:initial;background-origin:initial;background-clip:initial"><font face="arial, sans-serif" color="#000000">                   5th Floor, Room 530<b> </b></font></p><p class="MsoNormal" style="margin:0in;color:rgb(80,0,80);line-height:normal;background-image:initial;background-position:initial;background-size:initial;background-repeat:initial;background-origin:initial;background-clip:initial"><font face="arial, sans-serif"><b><span style="color:black"><br></span></b></font></p><p class="MsoNormal" style="margin:0in 0in 0.0001pt;line-height:normal;background-image:initial;background-position:initial;background-size:initial;background-repeat:initial;background-origin:initial;background-clip:initial"><b style="color:rgb(60,64,67);font-family:Roboto,Arial,sans-serif;letter-spacing:0.2px;white-space:pre-wrap">Virtually:</b><span style="font-size:14px;color:rgb(60,64,67);font-family:Roboto,Arial,sans-serif;letter-spacing:0.2px;white-space:pre-wrap">    via Panopto </span><a href="https://uchicago.hosted.panopto.com/Panopto/Pages/Viewer.aspx?id=72b5485e-fb43-4971-9a37-af3f0167d327" style="color:rgb(26,115,232);font-size:14px;font-family:Roboto,Arial,sans-serif;letter-spacing:0.2px;white-space:pre-wrap" target="_blank">(<b>livestream</b></a><span style="font-size:14px;color:rgb(60,64,67);font-family:Roboto,Arial,sans-serif;letter-spacing:0.2px;white-space:pre-wrap">)</span><br></p><p class="MsoNormal" style="margin:0in 0in 0.0001pt;color:rgb(80,0,80);line-height:normal;background-image:initial;background-position:initial;background-size:initial;background-repeat:initial;background-origin:initial;background-clip:initial"><font face="arial, sans-serif"><br></font></p><p class="MsoNormal" style="margin:0in 0in 0.0001pt;line-height:normal;background-image:initial;background-position:initial;background-size:initial;background-repeat:initial;background-origin:initial;background-clip:initial"><font face="arial, sans-serif"><font style="vertical-align:inherit"><font style="vertical-align:inherit"><font style="color:rgb(80,0,80)"><b>Who: </b> </font><font color="#500050" style="color:rgb(80,0,80)">    </font><font color="#000000"><font color="#500050">   </font></font></font></font></font>June Vuong, Stanford University</p><p class="MsoNormal" style="margin:0in 0in 0.0001pt;color:rgb(80,0,80);line-height:normal;background-image:initial;background-position:initial;background-size:initial;background-repeat:initial;background-origin:initial;background-clip:initial"><br></p><div class="MsoNormal" align="center" style="margin:0in 0in 8pt;font-size:11pt;text-align:center;line-height:15.6933px;font-family:Calibri,sans-serif"><hr size="2" width="100%" align="center"></div><div><p style="color:rgb(60,64,67);letter-spacing:0.2px;white-space:pre-wrap"><font face="arial, sans-serif"><span style="color:black;letter-spacing:normal"><b>Title:</b> Optimal Sublinear Sampling of Spanning Trees and Determinantal Point Processes via Average-Case Entropic Independence</span></font></p><div style="color:black;margin:0px"><font face="arial, sans-serif"><b>Abstract: </b>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})$.</font><div style="margin:0px"><font face="arial, sans-serif">            </font></div><font face="arial, sans-serif">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.</font></div><div style="color:black;margin:0px"><font face="arial, sans-serif">Joint work with Nima Anari and Yang P. Liu. To appear in FOCS 2022.</font></div><div style="color:black;margin:0px"><span style="font-family:arial,sans-serif">Arxiv link </span><a href="https://arxiv.org/abs/2204.02570v1" rel="noopener noreferrer" style="font-family:arial,sans-serif;margin:0px" target="_blank">[2204.02570v1] Optimal Sublinear Sampling of Spanning Trees and Determinantal Point Processes via Average-Case Entropic Independence (arxiv.org)</a><br></div><div dir="ltr"><span style="color:rgb(80,0,80)"><font face="arial, sans-serif"><div><br></div><div><br></div></font></span></div><b>Host: <a href="mailto:madhurt@ttic.edu" target="_blank">Madhur Tulsiani</a></b></div><div><br></div></div><div><div style="font-size:12.8px"><font face="arial, helvetica, sans-serif">**************************************************************************************************<br></font></div><div style="font-size:12.8px"><div><p class="MsoNormal" style="margin-bottom:0.0001pt;font-family:arial,sans-serif"><font face="arial, helvetica, sans-serif"> </font></p><p class="MsoNormal" style="margin-bottom:0.0001pt;font-family:arial,sans-serif"><font face="arial, helvetica, sans-serif">The <font color="#3d85c6"><i><b>TTIC Young Researcher Seminar Series</b></i></font> (<a href="http://www.ttic.edu/young-researcher.php" target="_blank">http://www.ttic.edu/young-researcher.php</a>) 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.</font></p><p class="MsoNormal" style="margin-bottom:0.0001pt;font-family:arial,sans-serif"><font face="arial, helvetica, sans-serif"><br>The seminars are typically held on Wednesdays at 10:30am in TTIC Room 530.<br><br>For additional information, please contact <i>David McAllester </i>(<a href="mailto:mcallester@ttic.edu" target="_blank">mcallester@ttic.edu</a>).</font></p><br></div></div></div></div><div><div dir="ltr"><div dir="ltr"><div><span style="font-family:arial,helvetica,sans-serif;font-size:x-small">Mary C. Marre</span><br></div><div><div><font face="arial, helvetica, sans-serif" size="1">Faculty Administrative Support</font></div><div><i><font face="arial, helvetica, sans-serif" color="#3d85c6" size="1"><b>Toyota Technological Institute</b></font></i></div><div><i><font face="arial, helvetica, sans-serif" color="#3d85c6" size="1">6045 S. Kenwood Avenue</font></i></div><div><font size="1"><i><font face="arial, helvetica, sans-serif" color="#3d85c6">Chicago, IL  60637</font></i><br></font></div><div><b><i><a href="mailto:mmarre@ttic.edu" target="_blank"><font face="arial, helvetica, sans-serif" size="1">mmarre@ttic.edu</font></a></i></b></div></div></div></div></div><br></div><br><div class="gmail_quote"><div dir="ltr" class="gmail_attr">On Mon, Oct 31, 2022 at 4:58 PM Mary Marre <<a href="mailto:mmarre@ttic.edu" target="_blank">mmarre@ttic.edu</a>> wrote:<br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><div dir="ltr"><div><div dir="ltr" style="font-size:small"><div style="font-family:arial,helvetica,sans-serif;font-size:12.8px"><font style="font-size:small;color:rgb(0,0,0);font-family:arial,sans-serif;vertical-align:inherit"><font style="vertical-align:inherit"><b style="color:rgb(34,34,34);background-color:rgb(255,255,0)"><font color="#000000">(</font><i style="color:rgb(0,0,0)">PLEASE NOTE SPECIAL TIME!)</i></b><b><br></b></font></font></div><div style="font-family:arial,helvetica,sans-serif;font-size:12.8px"><font style="font-size:small;color:rgb(0,0,0);font-family:arial,sans-serif;vertical-align:inherit"><font style="vertical-align:inherit"><b style="color:rgb(34,34,34);background-color:rgb(255,255,0)"><i style="color:rgb(0,0,0)"><br></i></b></font></font></div><div style="font-size:12.8px"><font style="font-family:arial,sans-serif;font-size:small;color:rgb(0,0,0);vertical-align:inherit"><font style="vertical-align:inherit"><b>When:</b>    </font></font><font style="font-size:small;vertical-align:inherit"><font style="vertical-align:inherit"><font face="arial, sans-serif" style="font-family:Arial,Helvetica,sans-serif;color:rgb(0,0,0)">    Monday</font><span class="gmail_default" style="font-family:arial,sans-serif;color:rgb(0,0,0)">, November 7th</span><font face="arial, sans-serif" style="font-family:Arial,Helvetica,sans-serif;color:rgb(0,0,0)"> at</font><font><b style="font-family:Arial,Helvetica,sans-serif;color:rgb(0,0,0)"> </b><b style="background-color:rgb(255,255,0)"><u><font color="#0000ff" face="verdana, sans-serif">3 </font></u></b></font><font face="verdana, sans-serif"><b style="background-color:rgb(255,255,0)"><u><font color="#0000ff">pm CT</font></u><font color="#000000">   </font></b></font></font></font><br></div></div><div><p style="font-size:small;color:rgb(80,0,80);font-variant-numeric:normal;font-variant-east-asian:normal;font-stretch:normal;line-height:normal;margin:0px"><font face="arial, sans-serif" color="#000000"><font style="vertical-align:inherit"><font style="vertical-align:inherit"><b><span style="background-color:rgb(255,255,0)"><br></span></b></font></font></font></p><div style="font-size:small"><font face="arial, sans-serif"><b><font color="#500050">Where:      </font><font color="#000000"> </font></b><font color="#000000">Talk will be given </font><font color="#0000ff" style="font-weight:bold"><u>live, in-person</u></font><font style="color:rgb(80,0,80);font-weight:bold"> </font><font style="color:rgb(80,0,80)">at</font></font></div><p class="MsoNormal" style="font-size:small;margin:0in;line-height:normal;background-image:initial;background-position:initial;background-size:initial;background-repeat:initial;background-origin:initial;background-clip:initial"><font face="arial, sans-serif"><font color="#500050">               </font><font color="#000000">    TTIC, 6045 S. Kenwood Avenue</font></font></p><p class="MsoNormal" style="font-size:small;margin:0in;line-height:normal;background-image:initial;background-position:initial;background-size:initial;background-repeat:initial;background-origin:initial;background-clip:initial"><font face="arial, sans-serif" color="#000000">                   5th Floor, Room 530<b> </b></font></p><p class="MsoNormal" style="font-size:small;margin:0in;color:rgb(80,0,80);line-height:normal;background-image:initial;background-position:initial;background-size:initial;background-repeat:initial;background-origin:initial;background-clip:initial"><font face="arial, sans-serif"><b><span style="color:black"><br></span></b></font></p><p class="MsoNormal" style="font-size:small;margin:0in 0in 0.0001pt;line-height:normal;background-image:initial;background-position:initial;background-size:initial;background-repeat:initial;background-origin:initial;background-clip:initial"><b style="color:rgb(60,64,67);font-family:Roboto,Arial,sans-serif;letter-spacing:0.2px;white-space:pre-wrap">Virtually:</b><span style="font-size:14px;color:rgb(60,64,67);font-family:Roboto,Arial,sans-serif;letter-spacing:0.2px;white-space:pre-wrap">    via Panopto </span><a href="https://uchicago.hosted.panopto.com/Panopto/Pages/Viewer.aspx?id=72b5485e-fb43-4971-9a37-af3f0167d327" style="color:rgb(26,115,232);font-size:14px;font-family:Roboto,Arial,sans-serif;letter-spacing:0.2px;white-space:pre-wrap" target="_blank">(<b>livestream</b></a><span style="font-size:14px;color:rgb(60,64,67);font-family:Roboto,Arial,sans-serif;letter-spacing:0.2px;white-space:pre-wrap">)</span><br></p><p class="MsoNormal" style="font-size:small;margin:0in 0in 0.0001pt;color:rgb(80,0,80);line-height:normal;background-image:initial;background-position:initial;background-size:initial;background-repeat:initial;background-origin:initial;background-clip:initial"><font face="arial, sans-serif"><br></font></p><p class="MsoNormal" style="font-size:small;margin:0in 0in 0.0001pt;line-height:normal;background-image:initial;background-position:initial;background-size:initial;background-repeat:initial;background-origin:initial;background-clip:initial"><font face="arial, sans-serif"><font style="vertical-align:inherit"><font style="vertical-align:inherit"><font style="color:rgb(80,0,80)"><b>Who: </b> </font><font color="#500050" style="color:rgb(80,0,80)">    </font><font color="#000000"><font color="#500050">   </font></font></font></font></font>June Vuong, Stanford University</p><p class="MsoNormal" style="font-size:small;margin:0in 0in 0.0001pt;color:rgb(80,0,80);line-height:normal;background-image:initial;background-position:initial;background-size:initial;background-repeat:initial;background-origin:initial;background-clip:initial"><br></p><div class="MsoNormal" align="center" style="font-size:11pt;margin:0in 0in 8pt;text-align:center;line-height:15.6933px;font-family:Calibri,sans-serif"><hr size="2" width="100%" align="center"></div><div><p style="color:rgb(60,64,67);letter-spacing:0.2px;white-space:pre-wrap"><font face="arial, sans-serif"><span style="color:black;letter-spacing:normal"><b>Title:</b> Optimal Sublinear Sampling of Spanning Trees and Determinantal Point Processes via Average-Case Entropic Independence</span></font></p><div style="color:black;margin:0px"><font face="arial, sans-serif"><b>Abstract: </b>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})$.</font><div style="margin:0px"><font face="arial, sans-serif">            </font></div><font face="arial, sans-serif">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.</font></div><div style="color:black;margin:0px"><font face="arial, sans-serif">Joint work with Nima Anari and Yang P. Liu. To appear in FOCS 2022.</font></div><div style="color:black;margin:0px"><span style="font-family:arial,sans-serif">Arxiv link </span><a href="https://arxiv.org/abs/2204.02570v1" rel="noopener noreferrer" style="font-family:arial,sans-serif;margin:0px" target="_blank">[2204.02570v1] Optimal Sublinear Sampling of Spanning Trees and Determinantal Point Processes via Average-Case Entropic Independence (arxiv.org)</a><br></div><div dir="ltr" style="font-size:small"><span style="color:rgb(80,0,80)"><font face="arial, sans-serif"><div><br></div><div><br></div></font></span></div><b style="font-size:small">Host: <a href="mailto:madhurt@ttic.edu" target="_blank">Madhur Tulsiani</a></b></div><div style="font-size:small"><br></div></div><div style="font-size:small"><div style="font-size:12.8px"><font face="arial, helvetica, sans-serif">**************************************************************************************************<br></font></div><div style="font-size:12.8px"><div><p class="MsoNormal" style="margin-bottom:0.0001pt;font-family:arial,sans-serif"><font face="arial, helvetica, sans-serif"> </font></p><p class="MsoNormal" style="margin-bottom:0.0001pt;font-family:arial,sans-serif"><font face="arial, helvetica, sans-serif">The <font color="#3d85c6"><i><b>TTIC <span>Young</span> <span>Researcher</span> <span>Seminar</span> <span>Series</span></b></i></font> (<a href="http://www.ttic.edu/young-researcher.php" target="_blank">http://www.ttic.edu/young-<span>researcher</span>.php</a>) features talks by Ph.D. students and postdocs whose research is of broad interest to the computer science community. The <span>series</span> provides an opportunity for early-career researchers to present recent work to and meet with students and faculty at TTIC and nearby universities.</font></p><p class="MsoNormal" style="margin-bottom:0.0001pt;font-family:arial,sans-serif"><font face="arial, helvetica, sans-serif"><br>The seminars are typically held on Wednesdays at 10:30am in TTIC Room 530.<br><br>For additional information, please contact <i>David McAllester </i>(<a href="mailto:mcallester@ttic.edu" target="_blank">mcallester@ttic.edu</a>).</font></p><p class="MsoNormal" style="margin-bottom:0.0001pt;font-family:arial,sans-serif"><font face="arial, helvetica, sans-serif"><br></font></p><p class="MsoNormal" style="margin-bottom:0.0001pt;font-family:arial,sans-serif"><font face="arial, helvetica, sans-serif"><br></font></p><font face="arial, helvetica, sans-serif"><br></font></div></div></div></div><div style="font-size:small"><br></div><div style="font-size:small"><br></div><div style="font-size:small"><br></div><div style="font-size:small"><br></div><div style="font-size:small"><br></div><div style="font-size:small">]</div><div style="font-size:small"><br></div><div><div dir="ltr"><div dir="ltr"><div><span style="font-family:arial,helvetica,sans-serif;font-size:x-small">Mary C. Marre</span><br></div><div><div><font face="arial, helvetica, sans-serif" size="1">Faculty Administrative Support</font></div><div><i><font face="arial, helvetica, sans-serif" color="#3d85c6" size="1"><b>Toyota Technological Institute</b></font></i></div><div><i><font face="arial, helvetica, sans-serif" color="#3d85c6" size="1">6045 S. Kenwood Avenue</font></i></div><div><font size="1"><i><font face="arial, helvetica, sans-serif" color="#3d85c6">Chicago, IL  60637</font></i><br></font></div><div><b><i><a href="mailto:mmarre@ttic.edu" target="_blank"><font face="arial, helvetica, sans-serif" size="1">mmarre@ttic.edu</font></a></i></b></div></div></div></div></div></div>
</blockquote></div></div>
</blockquote></div></div>
</blockquote></div></div>