Data that have an intrinsic network structure can be found in various contexts, including social networks, biological systems (e.g., protein-protein interactions, neuronal networks), information networks (computer networks, wireless sensor networks),  economic networks, etc. As the amount of graphical data that is generated is increasingly large, compressing such data for storage, transmission, or efficient processing has become a topic of interest. In this talk, I will give an information theoretic perspective on graph compression. 

The focus will be on compression limits and their scaling with the size of the graph. For lossless compression, the Shannon entropy gives the fundamental lower limit on the expected length of any compressed representation. I will discuss the entropy of some common random graph models, with a particular emphasis on our results on the random geometric graph model. 

Then, I will talk about the problem of compressing a graph with side information, i.e., when an additional correlated graph is available at the decoder. Turning to lossy compression, where one accepts a certain amount of distortion between the original and reconstructed graphs, I will present theoretical limits to lossy compression that we obtained for the Erdős–Rényi and stochastic block models by using rate-distortion theory.

I will give an overview of a recent method introduced by P. Duch to solve some subcritical singular SPDEs, in particular the stochastic quantisation equation for scalar fields. 

We consider the sharp interface limit problem for 1D stochastic Allen-Cahn equation, and extend a classic result by Funaki to the full small noise regime. One interesting point is that the notion of "small noise" turns out to depend on the topology one uses. The main new idea in the proof is the construction of a series of functional correctors, which are designed to recursively cancel out potential divergences. At a technical level, in order to show these correctors are well behaved, we also develop a systematic decomposition of functional derivatives of the deterministic Allen-Cahn flow of all orders, which might have its own interest.
Based on a joint work with Wenhao Zhao (EPFL) and Shuhan Zhou (PKU).

The positive discrepancy of a graph $G$ is the maximum surplus of edges in an induced subgraph of $G$ compared to its expected size. This quantity is closely related to other well studied parameters, such as the minimum bisection and the spectral gap. I will talk about the extremal behavior of the positive discrepancy among graphs with given number of vertices and average degree, uncovering a surprising pattern. This leads to an almost complete solution of a problem of Alon on the minimum bisection and let's us extend the Alon-Boppana bound on the second eigenvalue to dense graphs.

Joint work with Eero Räty and Benny Sudakov.