Talks

Abstract In this talk, I will present the multivariate normal approximation for the centered subgraph counts in dense random graphs. The main motivation to investigate these statistics is the fact that they are key to understanding fluctuations of regular subgraph counts since they act as an orthogonal basis of a corresponding L2 space. We also identify the resulting limiting Gaussian stochastic measures by means of the theory of generalised U-statistics and Gaussian Hilbert spaces, which we think is a suitable framework to describe and understand higher-order fluctuations in dense random graph models. This is joint work with Adrian Roellin.

In this talk  will develop Rafael D. Sorkin's heuristic that a partially ordered process of the birth of spacetime atoms in causal set quantum gravity can provide an objective physical correlate of our perception of time passing. I will argue that one cannot have an external, fully objective picture of the birth process because the order in which the spacetime atoms are born is a partial order. I propose that live experience in causal set theory is an internal ``view'' of the objective birth process in which events that are neural correlates of consciousness occur. In causal set theory, what ``breathes fire'' into a neural correlate of consciousness is that which breathes fire into the whole universe: the unceasing, partially ordered process of the birth of spacetime atoms.

Zoom link: https://pitp.zoom.us/j/95170823205?pwd=QW9YM3QrZU12Ti9HTUQ4TDlVNmN5Zz09

Abstract For any given graph $H$, one may define a natural corresponding functional $\|.\|_H$ for real(or complex) valued functions by using the homomorphism density of $H$. We say that $H$ is \emph{norming} if $\|.\|_H$ is a norm. This generalises the Gowers octahedral norms, a widely used tool in extremal combinatorics to quantify quasirandomness. In 2008, Lov\'{a}sz asked what graphs are norming. This has been a central question in the theory of dense graph limits and also connects to Sidorenko's conjecture, a major open problem in extremal graph theory. For the recent few years, there have been interesting developments on the Lovász question, where algebraic combinatorics, extremal graph theory and functional analysis meet. In this talk, I will discuss some of the progress. Based on joint work with David Conlon, Frederik Garbe, Jan Hladk\'{y}, Bjarne Sch\"{u}lke, and Sasha Sidorenko.

The degree-restricted random process is a natural algorithmic model for generating graphs with degree sequence D_n=(d_1,...,d_n): starting with an empty n-vertex graph, it sequentially adds new random edges so that the degree of each vertex v_i remains at most d_i.  It is natural to ask whether the final graph of this process is similar to a uniform random graph with degree sequence D_n (for d-regular degree sequences D_n this was already raised by Wormald in the mid 1990s). We show that, for degree sequences D_n that are not nearly regular, the final graph of the degree-restricted random process differs substantially from a uniform random graph with degree sequence D_n.  Our proof uses the switching method, which is usually only applied to uniform random graph models -- rather than to stochastic processes. Based on joint work with Mike Molloy and Erlang Surya.

The NLTS (No Low-Energy Trivial State) conjecture of Freedman and Hastings [2014] posits that there exist families of Hamiltonians with all low energy states of non-trivial complexity (with complexity measured by the quantum circuit depth preparing the state). Our recent work https://arxiv.org/abs/2206.13228 (with Nikolas Breuckmann and Chinmay Nirkhe) proves this conjecture by showing that the recently discovered families of constant-rate and linear-distance QLDPC codes correspond to NLTS local Hamiltonians. This talk will provide background on the conjecture, its relevance to quantum many-body physics and quantum complexity theory, and touch upon the proof techniques.

Zoom link: https://pitp.zoom.us/j/94224635225?pwd=SUovNXA3MWlkRUJlcTIxV0pLQzQxdz09

Abstract For a given graph H we are interested in the critical value of p so that a sample of an Erdos-Renyi graph contains a copy of H with high probability,  Kahn and Kalai in 2006 conjectured that it should be given (up to a logarithm) by the minimum p so that in expectation all subgraphs H' of H appear in G(n,p). In this work, we will present a proof of a modified version of this conjecture. Our proof is based on a powerful "spread lemma", which played a key role in the recent breakthroughs on the sunflower conjecture and the proof of the fractional Kahn-Kali conjecture. Time permitting, we will discuss a new proof of the spread lemma using Bayesian inference tools. This is joint work with Elchanan Mossel, Jonathan Niles-Weed and Nike Sun

Abstract It is well known that sparse random graphs (where the number of edges is of the order of the number of vertices) contain only a small number of triangles. On the other hand, many networks observed in real life are sparse but contain a large number of triangles. Motivated by this discrepancy we ask the following two questions: How (un)likely is it that a sparse random graph contains a large number of triangles? What does the graph look like when it contains a large number of triangles? We also ask a related question: What is the probability that in a sparse random graph a large number of vertices are part of some triangle? We discuss these questions, as well as some applications to exponential random graph models.

Abstract   In many domains, we are interested in estimating the total causal treatment effect in the presence of network interference, where the outcome of one individual or unit is affected by the treatment assignment of those in its local network. Additional challenges arise when complex cluster randomized designs are not feasible to implement, or the network is unknown and costly to estimate. We propose a new measure of model complexity that characterizes the difficulty of estimating the total treatment effect under the standard A/B testing setup. We provide a class of unbiased estimators whose variance is optimal with respect to the population size and the treatment budget. Furthermore, we show that when the network is completely unknown, we can still estimate the total treatment effect under a richer yet simple staggered rollout experimental design. The proposed design principles, and related estimator, work with a broad class of outcome models. Our solution and statistical guarantees do not rely on restrictive network properties, allowing for highly connected networks that may not be easily clustered. This is joint work with Edoardo Airoldi, Christian Borgs, Jennifer Chayes, Mayleen Cortez, and Matthew Eichhorn

Abstract A random structure exhibits symmetry if its law remains invariant under a group of transformations. Exchangeability (of graphs, sequences, etc) and stationarity are examples. Under suitable conditions, the transformation group can be used to define an estimator that averages over an instance of the structure, and such estimators turn out to satisfy a law of large numbers, a central limit theorem, and further convergence results. Loosely speaking: The large-sample theory of i.i.d averages still holds if the i.i.d assumption is substituted by a suitable symmetry assumption.  Joint work with Morgane Austern.