<html><head><meta http-equiv="Content-Type" content="text/html charset=windows-1252"></head><body style="word-wrap: break-word; -webkit-nbsp-mode: space; -webkit-line-break: after-white-space;">Folks,<div><br></div><div>Tomorrow (Friday 10 April) we are canceling YPNG because of a competing</div><div>talk that might be of interest to some of us:<br><div><br><div><blockquote type="cite"><div><div style="word-wrap: break-word; -webkit-nbsp-mode: space; -webkit-line-break: after-white-space;"><div><div><div><blockquote type="cite"><div bgcolor="#FFFFFF" text="#000000"><div class="moz-forward-container"><div style="font-family: Calibri, sans-serif; font-size: 14px;"><br>
</div>
<div style="font-family: Calibri, sans-serif; font-size: 14px;">
You’re cordially invited to attend a talk given by<b> Vahab
Mirrokni of Google:</b></div>
<div style="font-family: Calibri, sans-serif; font-size: 14px;">
<br>
</div>
<div><span style="font-size: 16px;"><i><b><span style="font-family: Calibri;">"Randomized
Composable Core-sets for Distributed Computation</span>”</b></i></span></div>
<div style="font-family: Calibri, sans-serif; font-size: 14px;">
<span style="font-family: Calibri; font-size: 12px;"><br>
</span></div>
<div><b>Friday, April 10th, 11am-12pm</b></div>
<span id="OLK_SRC_BODY_SECTION" style="font-family: Calibri, sans-serif;">
<div style="font-family: Calibri; font-style: normal; font-variant: normal; letter-spacing: normal; line-height: normal; orphans: auto; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; widows: auto; word-spacing: 0px; -webkit-text-stroke-width: 0px;">
<b>17 Hillhouse Avenue, 3rd Floor, Room 335</b></div>
<div style="font-family: Calibri; font-style: normal; font-variant: normal; letter-spacing: normal; line-height: normal; orphans: auto; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; widows: auto; word-spacing: 0px; -webkit-text-stroke-width: 0px;">
<b>Hosted by Amin Karbasi</b></div>
<div style="font-family: Calibri; font-style: normal; font-variant: normal; letter-spacing: normal; line-height: normal; orphans: auto; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; widows: auto; word-spacing: 0px; -webkit-text-stroke-width: 0px;">
<div style="font-weight: normal;"><br>
</div>
<div><b>Abstract: </b>An effective technique for solving
optimization problems over massive data sets is to partition
the data into smaller pieces, solve the problem on each
piece and compute a representative solution from it, and
finally obtain a solution inside the union of the
representative solutions for all pieces. Such an algorithm
can be implemented easily in 2 rounds of MapReduces or be
applied in an streaming model. This technique can be
captured via the concept of {\em composable core-sets}, and
has been recently applied to solve diversity maximization
problems as well as several clustering problems. However,
for coverage and submodular maximization problems,
impossibility bounds are known for this technique. In this
talk, after a initial discussion about this technique and
applications in diversity maximization and clustering
problems, we focus on the submodular maximization problem,
and show how to apply a randomized variant of composable
core-set problem, and achieve 1/3-approximation for monotone
and non-montone submodualr maximization problems. We prove
this result by applying a simple greedy algorithm and show
that a large class of algorithms can be deployed in this
framework. Time-permitting, we show a more complicated
algorithm that achieves 54% of the optimum in two rounds of
MapReduces.</div>
<div style="font-weight: normal;"><br>
</div>
<div style="font-weight: normal;">The main part of the talk is
to appear in STOC 2015 and is a joint work with Morteza
ZadiMoghaddam. The initial parts are from two recent papers
that appeared in PODS 2014 and NIPS 2014.</div>
<div style="font-weight: normal;"><br>
</div>
<div><b>Bio:</b><span style="font-weight: normal;"> Vahab
Mirrokni is a senior staff research scientist at
at Google Research NYC, where he is heading
the algorithms research group. He joined Google after
holding research positions at Microsoft Research, MIT and
Amazon. He received his PhD from MIT in 2005 and his B.Sc.
from Sharif University in 2001. Vahab's research
interests include large-scale graph mining,
approximation algorithms, and algorithmic game theory. At
Google, he is mainly working on algorithmic and economic
problems related to the internet search and online
advertising. As two of his recent projects, he is serving
a tech lead manager for the large-scale graph mining,
and market algorithms teams based in Google Research NYC.</span></div>
</div>
</span>
<div style="font-family: Calibri, sans-serif;"><br></div><div style="font-family: Calibri, sans-serif;">
<div style="font-size: 14px;"><a moz-do-not-send="true" href="http://yins.yale.edu/">http://yins.yale.edu</a></div>
</div>
<br>
</div>
<br>
</div>
</blockquote></div><br></div></div></div></div></blockquote></div><br></div></div><div>We do not yet have a talk arranged for April 17, but we want to bring to your attention another talk on that Friday,</div><div>to be given by Eric Denardo:</div><div><br></div><div></div></body></html>