<html xmlns:v="urn:schemas-microsoft-com:vml" xmlns:o="urn:schemas-microsoft-com:office:office" xmlns:w="urn:schemas-microsoft-com:office:word" xmlns:m="http://schemas.microsoft.com/office/2004/12/omml" xmlns="http://www.w3.org/TR/REC-html40"><head><META HTTP-EQUIV="Content-Type" CONTENT="text/html; charset=us-ascii"><meta name=Generator content="Microsoft Word 15 (filtered medium)"><style><!--
/* Font Definitions */
@font-face
{font-family:"Cambria Math";
panose-1:2 4 5 3 5 4 6 3 2 4;}
@font-face
{font-family:Calibri;
panose-1:2 15 5 2 2 2 4 3 2 4;}
/* Style Definitions */
p.MsoNormal, li.MsoNormal, div.MsoNormal
{margin:0in;
margin-bottom:.0001pt;
font-size:11.0pt;
font-family:"Calibri",sans-serif;}
a:link, span.MsoHyperlink
{mso-style-priority:99;
color:#0563C1;
text-decoration:underline;}
a:visited, span.MsoHyperlinkFollowed
{mso-style-priority:99;
color:#954F72;
text-decoration:underline;}
span.EmailStyle17
{mso-style-type:personal-compose;
font-family:"Calibri",sans-serif;
color:windowtext;}
.MsoChpDefault
{mso-style-type:export-only;}
@page WordSection1
{size:8.5in 11.0in;
margin:1.0in 1.0in 1.0in 1.0in;}
div.WordSection1
{page:WordSection1;}
--></style><!--[if gte mso 9]><xml>
<o:shapedefaults v:ext="edit" spidmax="1026" />
</xml><![endif]--><!--[if gte mso 9]><xml>
<o:shapelayout v:ext="edit">
<o:idmap v:ext="edit" data="1" />
</o:shapelayout></xml><![endif]--></head><body lang=EN-US link="#0563C1" vlink="#954F72"><div class=WordSection1><p class=MsoNormal>INSTITUTE FOR ADVANCED STUDY<o:p></o:p></p><p class=MsoNormal>School of Mathematics<o:p></o:p></p><p class=MsoNormal>Princeton, NJ 08540<o:p></o:p></p><p class=MsoNormal><o:p> </o:p></p><p class=MsoNormal>Theoretical Computer Science/Discrete Math Seminars<o:p></o:p></p><p class=MsoNormal>Week of January 28, 2019<o:p></o:p></p><p class=MsoNormal><o:p> </o:p></p><p class=MsoNormal><o:p> </o:p></p><p class=MsoNormal>--------------<o:p></o:p></p><p class=MsoNormal><b><span style='font-size:12.0pt'>***Please Note***<o:p></o:p></span></b></p><p class=MsoNormal><b><span style='font-size:12.0pt'>The Monday CSDM Seminars will now begin at <u>11:00AM</u>. <o:p></o:p></span></b></p><p class=MsoNormal>--------------<o:p></o:p></p><p class=MsoNormal><o:p> </o:p></p><p class=MsoNormal>Monday, January 28<o:p></o:p></p><p class=MsoNormal><o:p> </o:p></p><p class=MsoNormal>Computer Science/Discrete Mathematics Seminar I<o:p></o:p></p><p class=MsoNormal>Topic: PCP and Delegating Computation: A Love Story.<o:p></o:p></p><p class=MsoNormal>Speaker: Yael Tauman Kalai, Microsoft Research<o:p></o:p></p><p class=MsoNormal>Time/Room: 11:00am - 12:00pm/Simonyi Hall 101<o:p></o:p></p><p class=MsoNormal><span lang=FR>Abstract Link: </span><a href="http://www.math.ias.edu/seminars/abstract?event=128891"><span lang=FR>http://www.math.ias.edu/seminars/abstract?event=128891</span></a><span lang=FR><o:p></o:p></span></p><p class=MsoNormal><span lang=FR><o:p> </o:p></span></p><p class=MsoNormal><span lang=FR><o:p> </o:p></span></p><p class=MsoNormal><span lang=FR><o:p> </o:p></span></p><p class=MsoNormal>Monday, January 28<o:p></o:p></p><p class=MsoNormal><o:p> </o:p></p><p class=MsoNormal>Seminar on Theoretical Machine Learning<o:p></o:p></p><p class=MsoNormal>Speaker: No Seminar<o:p></o:p></p><p class=MsoNormal>Time/Room: 12:15pm - 1:45pm/No Seminar<o:p></o:p></p><p class=MsoNormal><o:p> </o:p></p><p class=MsoNormal><o:p> </o:p></p><p class=MsoNormal><o:p> </o:p></p><p class=MsoNormal><o:p> </o:p></p><p class=MsoNormal>Tuesday, January 29<o:p></o:p></p><p class=MsoNormal><o:p> </o:p></p><p class=MsoNormal>Computer Science/Discrete Mathematics Seminar II<o:p></o:p></p><p class=MsoNormal>Topic: A Regularity Lemma with Modifications<o:p></o:p></p><p class=MsoNormal>Speaker: Guy Moshkovitz, Member, School of Mathematics<o:p></o:p></p><p class=MsoNormal>Time/Room: 10:30am - 12:30pm/Simonyi Hall 101<o:p></o:p></p><p class=MsoNormal><span lang=FR>Abstract Link: </span><a href="http://www.math.ias.edu/seminars/abstract?event=129127"><span lang=FR>http://www.math.ias.edu/seminars/abstract?event=129127</span></a><span lang=FR><o:p></o:p></span></p><p class=MsoNormal><span lang=FR><o:p> </o:p></span></p><p class=MsoNormal>1 PCP and Delegating Computation: A Love Story. <br> Yael Tauman Kalai <br><br><br><o:p></o:p></p><p class=MsoNormal>In this talk, I will give an overview on how PCPs, combined with cryptographic tools, are used to generate succinct and efficiently verifiable proofs for the correctness of computations. I will focus on constructing (computationally sound) *succinct* proofs that are *non-interactive* (assuming the existence of public parameters) and are *publicly verifiable*. In particular, I will focus on a recent result with Omer Paneth and Lisa Yang, where we show how to construct such proofs for all polynomial time computations, based on an efficiently falsifiable decisional assumption on groups with bilinear maps. Prior to this work, this was only known under non-standard assumptions.<o:p></o:p></p><p class=MsoNormal><a href="http://www.math.ias.edu/seminars/abstract?event=128891">http://www.math.ias.edu/seminars/abstract?event=128891</a><br><br>2 A Regularity Lemma with Modifications <br> Guy Moshkovitz <br><br><br><o:p></o:p></p><p class=MsoNormal>Given an arbitrary graph, we show that if we are allowed to modify (say) 1% of the edges then it is possible to obtain a much smaller regular partition than in Szemeredi's original proof of the regularity lemma. Moreover, we show that it is impossible to improve upon the bound we obtain. <br><br>The upper bound can be used to reprove a famous result of Fox on the removal lemma [Ann. of Math. '11], whereas the lower bound served as a key step towards the solution of the optimality question for the hypergraph regularity lemma. Time permitting, we will give detailed sketches of both the upper and lower bound proofs. <br><br>Joint work with Asaf Shapira.<o:p></o:p></p><p class=MsoNormal><a href="http://www.math.ias.edu/seminars/abstract?event=129127">http://www.math.ias.edu/seminars/abstract?event=129127</a><br><br>Computer Science/Discrete Math Seminars can be found on our web page:<br><br><a href="http://www.math.ias.edu/csdm">http://www.math.ias.edu/csdm</a><br><a href="http://www.math.ias.edu">http://www.math.ias.edu</a><o:p></o:p></p></div></body></html>