[Colloquium] Reminder: Jones/MS Presentation/Oct 11, 2019
Margaret Jaffey
margaret at cs.uchicago.edu
Thu Oct 10 09:58:55 CDT 2019
This is a reminder about Chris Jones' MS Presentation tomorrow. Please
note it will be held in Crerar 298.
------------------------------------------------------------------------------
Date: Friday, October 11, 2019
Time: 2:00 PM
Place: John Crerar Library 298
M.S. Candidate: Christopher Jones
M.S. Paper Title: Spherical Discrepancy
Abstract:
Inspired by the boolean discrepancy problem, we study the following
optimization problem which we term \textsc{Spherical Discrepancy}:
given $m$ unit vectors $v_1, \dots, v_m$, find another unit vector $x$
that minimizes $\max_i \innerproduct{x}{v_i}$. We show that
\textsc{Spherical Discrepancy} is APX-hard and develop a
multiplicative weights-based algorithm that achieves nearly optimal
worst-case error bounds. We use our algorithm to give the first
non-trivial lower bounds for the problem of covering a hypersphere by
hyperspherical caps of uniform volume at least $2^{-o(\sqrt{n})}$, and
to give a lower bound for covering a Gaussian random variable by
equal-sized halfspaces. Up to a log factor, our lower bounds match
known upper bounds in this regime.
Christopher's advisor is Prof. Andrew Drucker
Login to the Computer Science Department website for details:
https://newtraell.cs.uchicago.edu/phd/ms_announcements#csj
=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=
Margaret P. Jaffey margaret at cs.uchicago.edu
Department of Computer Science
Student Support Rep (Ry 156) (773) 702-6011
The University of Chicago http://www.cs.uchicago.edu
=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=
More information about the Colloquium
mailing list