[Theory] [Theory Lunch] ROOM CHANGE: Ali Vakilian, Wednesday, 10/9 12-1pm, JCL 298

[Gabe Schoenbach via Theory]

Hi all — please note that this week only, theory lunch will be held in *JCL
298*. See you soon!

On Mon, Oct 7, 2024 at 10:51 AM Gabe Schoenbach <gschoenbach at uchicago.edu>
wrote:

> Hi all — please join us this *Wednesday at 12pm* for theory lunch! (Note
> the half-hour earlier start time this year). Details below:
>
> *****
> *Date: *October 9, 2024
> *Time: *12:00pm
> *Location: *JCL 390
>
> *Title: *Tight Bounds for Volumetric Spanners and Applications
>
> *Speaker: *Ali Vakilian, TTIC
>
> *Abstract:* 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.
>
> Joint work with Aditya Bhaskara (University of Utah) and Sepideh Mahabadi
> (Microsoft Research--Redmond).
>


-- 
*Gabe Schoenbach* (he)
PhD Student, Computer Science
The University of Chicago
(707) 779-9131 | gabey.zip
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mailman.cs.uchicago.edu/pipermail/theory/attachments/20241009/6617dcdc/attachment.html>