<html>
<head>
<meta http-equiv="content-type" content="text/html; charset=utf-8">
</head>
<body bgcolor="#FFFFFF" text="#000000">
<br>
<div class="moz-forward-container"><br>
<br>
-------- Forwarded Message --------
<table class="moz-email-headers-table" border="0" cellpadding="0"
cellspacing="0">
<tbody>
<tr>
<th align="RIGHT" nowrap="nowrap" valign="BASELINE">Subject:
</th>
<td>[Theory-Read] Fwd: [ORFE-Seminars] Princeton
Optimization Seminar, Jelani Nelson, Today, Apr. 27, 4:30
PM, Sherrerd 101</td>
</tr>
<tr>
<th align="RIGHT" nowrap="nowrap" valign="BASELINE">Date: </th>
<td>Thu, 27 Apr 2017 13:21:03 +0000</td>
</tr>
<tr>
<th align="RIGHT" nowrap="nowrap" valign="BASELINE">From: </th>
<td>Amir Ali Ahmadi <a class="moz-txt-link-rfc2396E" href="mailto:a_a_a@princeton.edu"><a_a_a@princeton.edu></a></td>
</tr>
<tr>
<th align="RIGHT" nowrap="nowrap" valign="BASELINE">To: </th>
<td><a class="moz-txt-link-abbreviated" href="mailto:theory-read@lists.cs.princeton.edu">theory-read@lists.cs.princeton.edu</a>
<a class="moz-txt-link-rfc2396E" href="mailto:theory-read@lists.cs.princeton.edu"><theory-read@lists.cs.princeton.edu></a></td>
</tr>
</tbody>
</table>
<br>
<br>
<meta http-equiv="Content-Type" content="text/html; charset=utf-8">
<div><br>
<br>
Sent from my iPhone</div>
<div><br>
Begin forwarded message:<br>
<br>
</div>
<blockquote type="cite">
<div><b>From:</b> Carol Smith <<a moz-do-not-send="true"
href="mailto:carols@princeton.edu">carols@PRINCETON.EDU</a>><br>
<b>Date:</b> April 27, 2017 at 8:51:51 AM EDT<br>
<b>To:</b> <<a moz-do-not-send="true"
href="mailto:ORFE-TALKS@princeton.edu">ORFE-TALKS@Princeton.EDU</a>><br>
<b>Subject:</b> <b>[ORFE-Seminars] Princeton Optimization
Seminar, Jelani Nelson, Today, Apr. 27, 4:30 PM, Sherrerd
101</b><br>
<b>Reply-To:</b> Carol Smith <<a moz-do-not-send="true"
href="mailto:carols@princeton.edu">carols@PRINCETON.EDU</a>><br>
<br>
</div>
</blockquote>
<blockquote type="cite">
<div>
<div style="font-family: "Segoe UI", Helvetica,
Arial, sans-serif; font-size: medium; margin: 0px;">
<font face="Calibri,sans-serif" size="2"><span
style="font-size: 11pt;"><font face="Tahoma,sans-serif"><b>-----
</b></font><font face="Tahoma,sans-serif"><b><u>Princeton
Optimization Seminar</u></b></font><font
face="Tahoma,sans-serif"><b> -----</b></font></span></font></div>
<div style="font-family: "Segoe UI", Helvetica,
Arial, sans-serif; font-size: medium; margin: 0px;">
<font face="Calibri,sans-serif" size="2"><span
style="font-size: 11pt;"><font color="black"
face="Tahoma,sans-serif"><br>
</font><font color="black" face="Tahoma,sans-serif"><span
style="background-color: white;"><b>DATE: </b></span></font><font
color="black" face="Tahoma,sans-serif" size="3"><span
style="font-size: 12pt; background-color: white;">Today,
April 27, 2017</span></font><font color="black"
face="Tahoma,sans-serif"><span
style="background-color: white;"><br>
</span></font><font color="black"
face="Tahoma,sans-serif"><br>
</font><font color="black" face="Tahoma,sans-serif"><span
style="background-color: white;"><b>TIME</b></span></font><font
color="black" face="Tahoma,sans-serif" size="3"><span
style="font-size: 12pt; background-color: white;">:
4:30PM</span></font><font color="black"
face="Tahoma,sans-serif"><span
style="background-color: white;"> </span></font><font
color="black" face="Tahoma,sans-serif"><br>
</font><font color="black" face="Tahoma,sans-serif"><br>
</font><font color="black" face="Tahoma,sans-serif"><span
style="background-color: white;"><b>LOCATION</b></span></font><font
color="black" face="Tahoma,sans-serif" size="3"><span
style="font-size: 12pt; background-color: white;"><b>: </b></span></font><font
color="black" face="Tahoma,sans-serif" size="3"><span
style="font-size: 12pt; background-color: white;"> Sherrerd
Hall 101</span></font><font color="black"
face="Tahoma,sans-serif"><br>
</font><font color="black" face="Tahoma,sans-serif"><br>
</font><font color="black" face="Tahoma,sans-serif"><span
style="background-color: white;"><b>SPEAKER:</b></span></font><font
color="black" face="Tahoma,sans-serif"><span
style="background-color: white;">
</span></font></span></font><font
face="Tahoma,sans-serif" size="+1">Jelani Nelson, Harvard
University</font></div>
<div style="font-family: "Segoe UI", Helvetica,
Arial, sans-serif; font-size: medium; margin: 0px;">
<font face="Calibri,sans-serif" size="2"><span
style="font-size: 11pt;"><font color="black"
face="Tahoma,sans-serif" size="2"><span
style="font-size: 10pt;"> </span></font></span></font></div>
<div style="font-family: "Segoe UI", Helvetica,
Arial, sans-serif; font-size: medium; margin: 0px;">
<font face="Calibri,sans-serif" size="2"><span
style="font-size: 11pt;"><font color="black"
face="Tahoma,sans-serif"><span
style="background-color: white;"><b>TITLE:
</b></span></font><font color="black"
face="Tahoma,sans-serif" size="3"><span
style="font-size: 12pt; background-color: white;">Optimality
of the Johnson-Lindenstrauss Lemma
<br>
</span></font></span></font></div>
<div style="font-family: "Segoe UI", Helvetica,
Arial, sans-serif; font-size: medium; margin: 0px;">
<font face="Calibri,sans-serif" size="2"><span
style="font-size: 11pt;"><font color="black"
face="Tahoma,sans-serif" size="2"><span
style="font-size: 10pt;"> </span></font></span></font></div>
<font face="Calibri,sans-serif" size="2"><span
style="font-size: 11pt;"><font color="black"
face="Tahoma,sans-serif" size="3"><span
style="font-size: 12pt;"><b>Abstract:
</b>Dimensionality reduction in Euclidean space, as
attainable by the Johnson-Lindenstrauss lemma (also
known as "random projections"), has been a fundamental
tool in algorithm design and machine learning. The JL
lemma states that any n points in Euclidean space can
be mapped to m-dimensional Euclidean space while
preserving all pairwise distances up to 1+epsilon,
where m only needs to be on the order of (log n) /
epsilon^2, independent of the original dimension. In
this talk, I discuss our recent proof that the JL
lemma is optimal, in the sense that for any n there
are point sets of size n such that no embedding
providing (1+epsilon)-distortion exists into a
dimension that is more than a constant factor better
than what the JL lemma guarantees. I will also discuss
some subsequent work and future directions. Joint work
with Kasper Green Larsen (Aarhus University).<br>
<br>
<b>BIO:</b> Jelani Nelson is an Assistant Professor of
Computer Science at Harvard University. His main
research interest is in algorithm design and analysis,
with recent focus on streaming algorithms,
dimensionality reduction, compressed sensing, and
randomized linear algebra algorithms. He completed his
Ph.D. in computer science at MIT in 2011, receiving
the George M. Sprowls Award for best computer science
doctoral dissertations at MIT. He is the recipient of
an NSF CAREER Award, ONR Young Investigator Award, ONR
Director of Research Early Career Award, Alfred P.
Sloan Research Fellowship, and Presidential Early
Career Award for Scientists and Engineers (PECASE).</span></font></span></font>
</div>
</blockquote>
<br>
</div>
<br>
</body>
</html>