# [YPNG] YPNG in April (and two non-YPNG talks of interest)

David Pollard david.pollard at yale.edu
Thu Apr 9 12:09:58 EDT 2015

Folks,

Tomorrow (Friday 10 April) we are canceling YPNG because of a competing
talk that might be of interest to some of us:

>>
>> You’re cordially invited to attend a talk given by Vahab Mirrokni of Google:
>>
>> "Randomized Composable Core-sets for Distributed Computation”
>>
>> Friday, April 10th, 11am-12pm
>> 17 Hillhouse Avenue, 3rd Floor, Room 335
>> Hosted by Amin Karbasi
>>
>> Abstract: 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.
>>
>> 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.
>>
>> Bio: 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.
>>
>> http://yins.yale.edu
>>
>>
>

We do not yet have a talk arranged for April 17, but we want to bring to your attention another talk on that Friday,
to be given by Eric Denardo:

David
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://mailman.yale.edu/pipermail/ypng/attachments/20150409/a12b7aec/attachment-0002.html
-------------- next part --------------
A non-text attachment was scrubbed...
Name: Denardo.pdf
Type: application/pdf
Size: 148907 bytes
Desc: not available
Url : http://mailman.yale.edu/pipermail/ypng/attachments/20150409/a12b7aec/attachment-0001.pdf
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://mailman.yale.edu/pipermail/ypng/attachments/20150409/a12b7aec/attachment-0003.html