<div dir="ltr"><div>Hi all — please note that this week only, theory lunch will be held in <b>JCL 298</b>. See you soon!</div><br><div class="gmail_quote"><div dir="ltr" class="gmail_attr">On Mon, Oct 7, 2024 at 10:51 AM Gabe Schoenbach <<a href="mailto:gschoenbach@uchicago.edu">gschoenbach@uchicago.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">Hi all — please join us this <b>Wednesday at 12pm</b> for theory lunch! (Note the half-hour earlier start time this year). Details below:<div><br></div><div>*****</div><div><b>Date: </b>October 9, 2024</div><div><b>Time: </b>12:00pm</div><div><b>Location: </b>JCL 390</div><div><br></div><div><div><b>Title: </b>Tight Bounds for Volumetric Spanners and Applications</div><div><br></div><div><b>Speaker: </b>Ali Vakilian, TTIC</div><div><br></div><div><b>Abstract:</b> Given a set of points of interest, a volumetric spanner is a subset of the points using which all the points can be expressed using "small" coefficients (measured in an appropriate norm). Formally, given a set of vectors $X = \{v_1, v_2, \dots, v_n\}$, the goal is to find $T \subseteq [n]$ such that every $v \in X$ can be expressed as $\sum_{i\in T} \alpha_i v_i$, with $||\alpha||$ being small.  This notion, which has also been referred to as a well-conditioned basis, has found several applications, including bandit linear optimization, determinant maximization, and matrix low rank approximation. In this paper, we give almost optimal bounds on the size of volumetric spanners for all $\ell_p$ norms, and show that they can be constructed using a simple local search procedure. We then show the applications of our result to other tasks and in particular the problem of finding coresets for the Minimum Volume Enclosing Ellipsoid (MVEE) problem.<br></div><div><br></div><div>Joint work with Aditya Bhaskara (University of Utah) and Sepideh Mahabadi (Microsoft Research--Redmond). </div></div><div><div dir="ltr" class="gmail_signature"><div dir="ltr"><div><div dir="ltr"></div></div></div></div></div></div>
</blockquote></div><br clear="all"><div><br></div><span class="gmail_signature_prefix">-- </span><br><div dir="ltr" class="gmail_signature"><div dir="ltr"><div><div dir="ltr"><b>Gabe Schoenbach</b> (he)</div><div dir="ltr">PhD Student, Computer Science</div><div dir="ltr"><div>The University of Chicago</div><div>(707) 779-9131 | <a href="https://gabey.zip" target="_blank">gabey.zip</a></div></div></div></div></div></div>