<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;">&nbsp;Vahab
              Mirrokni is a senior staff research scientist at
              at&nbsp;Google&nbsp;Research NYC, where he is heading
              the&nbsp;algorithms&nbsp;research group. He joined&nbsp;Google&nbsp;after
              holding research positions at&nbsp;Microsoft&nbsp;Research, MIT and
              Amazon.&nbsp;He received his PhD from&nbsp;MIT&nbsp;in 2005 and his B.Sc.
              from Sharif University in 2001.&nbsp; Vahab's research
              interests include large-scale graph mining,
              approximation&nbsp;algorithms, and&nbsp;algorithmic&nbsp;game theory.&nbsp;At
              Google, he is mainly working on&nbsp;algorithmic&nbsp;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&nbsp;large-scale graph mining,
              and&nbsp;market&nbsp;algorithms&nbsp;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>