[Colloquium] REMINDER: 5/17 Research at TTIC: Sanjeev Khanna, University of Pennsylvania

[Alicia McClarin]

*When:*     Friday, May 17th. Refreshments at noon. Talk begins at 12:20pm.

*Where:*    TTIC, 6045 S Kenwood Avenue, 5th Floor, Room 526

*Who: *      Sanjeev Khanna, University of Pennsylvania

*Title: *       Sublinear Algorithms for Graph Coloring

*Abstract: *In this talk, we will examine a classical graph coloring
problem through the lens of sublinear algorithms—these are algorithms that
use computational resources that are substantially smaller than the size of
the input on which they operate. It is well-known that any graph with
maximum degree Delta admits a proper vertex coloring with (Delta + 1)
colors that can be found via a simple sequential greedy algorithm in linear
time and space. But can one find such a coloring via a sublinear algorithm?
In this talk, we will present results that answer this question in the
affirmative for several well-studied models of sublinear computation
including graph streaming, sublinear time, and massively parallel
computation (MPC). We obtain these results by proving a palette
sparsification theorem which says that if every vertex independently
samples O(log n) colors, then almost certainly a (Delta + 1) coloring can
be found using only the sampled colors. We will show that this palette
sparsification theorem naturally leads to essentially optimal sublinear
algorithms in each of the above-mentioned models of computation.

This is based on joint work with Sepehr Assadi and Yu Chen.
********************************************************************************************************

*Research at TTIC Seminar Series*

TTIC is hosting a weekly seminar series presenting the research currently
underway at the Institute. Every week a different TTIC faculty member will
present their research.  The lectures are intended both for students
seeking research topics and adviser, and for the general TTIC and
University of Chicago communities interested in hearing what their
colleagues are up to.

To receive announcements about the seminar series, please subscribe to the
mailing list: https://groups.google.com/a/ttic.edu/group/talks/subscribe

Speaker details can be found at: http://www.ttic.edu/tticseminar.php.

For additional questions, please contact Nathan Srebro at nati at ttic.edu
<mcallester at ttic.edu>

-- 
*Alicia McClarin*
*Toyota Technological Institute at Chicago*
*6045 S. Kenwood Ave., **Office 518*
*Chicago, IL 60637*
*www.ttic.edu* <http://www.ttic.edu/>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mailman.cs.uchicago.edu/pipermail/colloquium/attachments/20190516/e2b8e763/attachment-0001.html>