[iasmath-seminars] Theoretical Computer Science/Discrete Math Seminars-Week of March 11, 2019

[Kristina Phillips]

INSTITUTE FOR ADVANCED STUDY

School of Mathematics

Princeton, NJ 08540

 

Theoretical Computer Science/Discrete Math Seminars

Week of March 11, 2019

 

 

--------------

To view mathematics in titles and abstracts, please click on the talk's link.

--------------

 

Monday, March 11

 

Computer Science/Discrete Mathematics Seminar I

Topic:                    Near log-convexity of measured heat in (discrete) time and consequences

Speaker:              Mert Sağlam, University of Washington

Time/Room:       11:00am - 12:00pm/Simonyi Hall 101

Abstract Link:     http://www.math.ias.edu/seminars/abstract?event=128909

 

 

 

Monday, March 11

 

Seminar on Theoretical Machine Learning

Topic:                    TBA

Speaker:              TBA

Time/Room:       12:15pm - 1:45pm/White Levy Room

 

 

 

 

Tuesday, March 12

 

Computer Science/Discrete Mathematics Seminar II

Topic:                   Halting problems for sandpiles and abelian networks

Speaker:              Lionel Levine, Cornell University; von Neumann Fellow

Time/Room:       10:30am - 12:30pm/Simonyi Hall 101

Abstract Link:     http://www.math.ias.edu/seminars/abstract?event=129145

 

 

 

1 Near log-convexity of measured heat in (discrete) time and consequences 
   Mert Sağlam 



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)$.

http://www.math.ias.edu/seminars/abstract?event=128909

 



2 Halting problems for sandpiles and abelian networks
   Lionel Levine 



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. 

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. 

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. 

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. 

Is abelian computation weaker than Turing computation? If time permits, I’ll tell you what I know about this maddening question! 

If time still 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. 

I will not answer any questions about hats. 

Joint work with Ben Bond, Matt Farrell, Alexander Holroyd, and Peter Winkler.

http://www.math.ias.edu/seminars/abstract?event=129145

Computer Science/Discrete Math Seminars can be found on our web page:

http://www.math.ias.edu/csdm
http://www.math.ias.edu

 

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://imap.math.ias.edu/pipermail/iasmathsemo/attachments/20190307/64f85496/attachment-0001.html>