[Colloquium] Jones/MS Presentation/Oct 4, 2019

[Margaret Jaffey]

This is an announcement of Christopher Jones's MS Presentation.

------------------------------------------------------------------------------
Date:  Friday, October 4, 2019

Time:  1:30 PM

Place:  John Crerar Library 390

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
=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=