<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=utf-8"><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;}
p.msonormal0, li.msonormal0, div.msonormal0
{mso-style-name:msonormal;
mso-margin-top-alt:auto;
margin-right:0in;
mso-margin-bottom-alt:auto;
margin-left:0in;
font-size:12.0pt;
font-family:"Times New Roman",serif;}
span.EmailStyle18
{mso-style-type:personal-compose;
font-family:"Calibri",sans-serif;
color:windowtext;}
span.EmailStyle19
{mso-style-type:personal;
font-family:"Calibri",sans-serif;
color:windowtext;}
.MsoChpDefault
{mso-style-type:export-only;
font-size:10.0pt;}
@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><b>Theoretical Computer Science/Discrete Math Seminars<o:p></o:p></b></p><p class=MsoNormal><b>Week of March 11, 2019<o:p></o:p></b></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>To view mathematics in titles and abstracts, please click on the talk's link.<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>Monday, March 11<o:p></o:p></b></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: Near log-convexity of measured heat in (discrete) time and consequences<o:p></o:p></p><p class=MsoNormal>Speaker: Mert Sağlam, University of Washington<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>Abstract Link: <a href="http://www.math.ias.edu/seminars/abstract?event=128909">http://www.math.ias.edu/seminars/abstract?event=128909</a><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>Monday, March 11<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>Topic: TBA<o:p></o:p></p><p class=MsoNormal>Speaker: TBA<o:p></o:p></p><p class=MsoNormal>Time/Room: 12:15pm - 1:45pm/White Levy Room<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><b>Tuesday, March 12<o:p></o:p></b></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: Halting problems for sandpiles and abelian networks<o:p></o:p></p><p class=MsoNormal>Speaker: Lionel Levine, Cornell University; von Neumann Fellow<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>Abstract Link: <a href="http://www.math.ias.edu/seminars/abstract?event=129145">http://www.math.ias.edu/seminars/abstract?event=129145</a><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 style='margin-bottom:12.0pt'>1 Near log-convexity of measured heat in (discrete) time and consequences <br> Mert Sağlam <br><br><o:p></o:p></p><p class=MsoNormal>We answer a 1982 conjecture of Erd&#337;s and Simonovits about the growth of number of $k$-walks in a graph, which incidentally was studied earlier by Blakley and Dixon in 1966. We prove this conjecture in a more general setup than the earlier treatment, furthermore, through a refinement and strengthening of this inequality, we resolve two related open questions in complexity theory: the communication complexity of the $k$-Hamming distance is $\Omega(k \log k)$ and that consequently any property tester for k-linearity requires $\Omega(k \log k)$.<o:p></o:p></p><p class=MsoNormal style='margin-bottom:12.0pt'><a href="http://www.math.ias.edu/seminars/abstract?event=128909">http://www.math.ias.edu/seminars/abstract?event=128909</a><o:p></o:p></p><p class=MsoNormal style='margin-bottom:12.0pt'><o:p> </o:p></p><p class=MsoNormal style='margin-bottom:12.0pt'><br><br>2 Halting problems for sandpiles and abelian networks<br> Lionel Levine <br><br><o:p></o:p></p><p class=MsoNormal>Will this procedure be finite or infinite? If finite, how long can it last? Bjorner, Lovasz, and Shor asked these questions in 1991 about the following procedure, which goes by the name “abelian sandpile”: Given a configuration of chips on the vertices of a finite directed graph, choose (however you like) a vertex with at least as many chips as out-neighbors, and send one chip from that vertex to each of its out-neighbors. Repeat, until there is no such vertex. <br><br>The first part of the talk will be a little tour of “algebraic directed graph theory”, whose main player is the graph Laplacian considered as an *integer* matrix. I’ll tell you about the curious class of coEulerian graphs, for which sandpile halting is easy to decide even though it may require exponentially many steps. A recent theorem of Nguyen and Wood, confirming a conjecture of Koplewitz, shows that coEulerian graphs are not rare: The directed random graph G(n,p) is coEulerian with limiting probability $1/(\zeta(2)\zeta(3)\zeta(4)\cdots )$ where $\zeta$ is the Riemann zeta function. So (in case you were wondering) about 43.6% of all simple directed graphs are coEulerian. <br><br>The second part of the talk will focus on computation in abelian networks. These are automata networks, generalizing the abelian sandpile, for which the order of execution does not affect the final output. I’ll state some “local-to-global principles” of the form: If every automaton has property X, then the whole network has X. <br><br>The usual Boolean gates are not abelian, but there is a set of simple "abelian logic gates” that suffice to compute any abelian function. These include an infinite family, indexed by prime numbers $p$, computing $x \mapsto \lfloor x/p \rfloor$. For directed acyclic circuits, no finite set of abelian gates suffices. But for circuits allowing a limited type of feedback, a specific set of five gates suffices. <br><br>Is abelian computation weaker than Turing computation? If time permits, I’ll tell you what I know about this maddening question! <br><br>If time <i>still</i> permits, I’ll return to the abelian sandpile to tell you about some of the “critical exponents” physicists would like to calculate. Discrete Fourier techniques may be useful here. <br><br>I will not answer any questions about hats. <br><br>Joint work with Ben Bond, Matt Farrell, Alexander Holroyd, and Peter Winkler.<o:p></o:p></p><p class=MsoNormal><a href="http://www.math.ias.edu/seminars/abstract?event=129145">http://www.math.ias.edu/seminars/abstract?event=129145</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><p class=MsoNormal><o:p> </o:p></p></div></body></html>