## Events

**past events**and here for a presentation of the Rome Centre on Mathematics for Modelling and Data ScienceS.

If you want to receive updates on RoMaDS activities, write an email to salvi(at)mat.uniroma2.it to be added to our

**mailing list**.

**Upcoming events**

**16.10.2024 - Seminar: Alessandra Bianchi (University of Padova)**, Mixing cutoff for simple random walks on the Chung-Lu directed graph

14h00-15h00, Department of Mathematics, Aula D'Antoni.

Teams streaming link

## Abstract

In this talk, we consider a simple random walk defined on a Chung-Lu directed graph, an inhomogeneous random network that extends the Erdos Renyi random digraph by including edges independently according to given Bernoulli laws. In this non-reversible setting, we will focus on the convergence toward the equilibrium of the dynamics. In particular, under the assumption that the average degree grows logarithmically in the size n of the graph (weakly dense regime), we will establish a cutoff phenomenon at the entropic time of order log(n)/loglog(n). We will then show that on a precise window the cutoff profile converges to the Gaussian tail function. This is qualitatively similar to what was proved in a series of works by Bordenave, Caputo, Salez for the directed configuration model, where degrees are deterministically fixed. In terms of statistical ensembles, this analysis provides an extension of these cutoff results from a hard to a soft-constrained model. Joint work with G. Passuello.

**30.10.2024 - Lecture: Andrea Clementi and Francesco Pasquale (Tor Vergata University)**, A preparatory lecture to Avi Wigderson's seminar

14h00-16h00, Department of Mathematics, Aula Dal Passo.

**31.10.2024 - Colloquium: Avi Wigderson (Princeton University)**, The Value of Errors in Proofs - The fascinating journey from Turing's 1936 R ≠ RE to the 2020 breakthrough of MIP* = RE

15h00-16h00, Department of Mathematics, Aula Gismondi.

Website of the event.

Teams streaming link.

## Abstract

In 2020, a group of theoretical computer scientists posted a paper on the Arxiv with the strange-looking title "MIP* = RE", impacting and surprising not only complexity theory but also some areas of math and physics. Specifically, it resolved, in the negative, the "Connes' embedding conjecture" in the area of von-Neumann algebras, and the "Tsirelson problem" in quantum information theory. You can find the paper here. As it happens, both acronyms MIP* and RE represent proof systems, of a very different nature. To explain them, we'll take a meandering journey through the classical and modern definitions of proof. I hope to explain how the methodology of computational complexity theory, especially modeling and classification (both problems and proofs) by algorithmic efficiency, naturally leads to the generation of new such notions and results (and more acronyms, like NP). A special focus will be on notions of proof which allow interaction, randomness, and errors, and their surprising power and magical properties, including ZK (Zero Knowledge proofs) and PCPs (Probababilistically Checkable Proofs). The talk will be non-technical, and requires no special background.