Tel Aviv University

Let $G$ be a $d$-regular graph of growing degree on $n$ vertices. Form a random subgraph $G_p$ of $G$ by retaining edge of $G$ independently with probability $p=p(d)$. Which conditions on $G$ suffice to observe a phase transition at $p=1/d$, similar to that in the binomial random graph $G(n,p)$, or, say, in a random subgraph of the binary hypercube $Q^d$?

We argue that in the supercritical regime $p=(1+\epsilon)/d$, $\epsilon>0$ a small constant, postulating that every vertex subset $S$ of $G$ of at most $n/2$ vertices has its edge boundary at least $C|S|$, for some large enough constant $C=C(\epsilon)>0$, suffices to guarantee likely appearance of the giant component in $G_p$. Moreover, its asymptotic order is equal to that in the random graph $G(n,(1+\epsilon)/n)$, and all other components are typically much smaller.

We also give examples demonstrating tightness of our main result in several key senses.

A joint work with Sahar Diskin, Joshua Erde and Mihyun Kang.

Let $G$ be a $d$-regular graph of growing degree on $n$ vertices, and form a random subgraph $G_p$ of $G$ by retaining edge of $G$ independently with probability $p=p(d)$. Which conditions on $G$ suffice to observe a phase transition at $p=1/d$, similar to that in the binomial random graph $G(n,p)$, or, say, in a random subgraph of the binary hypercube $Q^d$?

We argue that in the supercritical regime $p=(1+\epsilon)/d$, $\epsilon>0$ being a small constant, postulating that every vertex subset $S$ of $G$ of at most $n/2$ vertices has its edge boundary at least $C|S|$, for some large enough constant $C=C(\epsilon)>0$, suffices to guarantee the likely appearance of the giant component in $G_p$. Moreover, its asymptotic order is equal to that in the random graph $G(n,(1+\epsilon)/n)$, and all other components are typically much smaller.

We further give examples demonstrating the tightness of this result in several key senses.

A joint work with Sahar Diskin, Joshua Erde and Mihyun Kang.

A growing plant is a fascinating system involving multiple fields. Biologically, it is a multi-cellular system controlled by bio-chemical networks. Physically, it is an example of an "active solid" whose element (cells) are active, performing mechanical work to drive the evolving geometry. Computationally, it is a distributed system, processing a multitude of local inputs into a coordinated developmental response. In this talk I will discuss how plants, a living information-processing organism, uses physical laws and biological mechanisms to alter its own shape, and negotiate its environment. Here I will focus on two examples reflecting the computational and mechanical aspects: (i) probing temporal integration in gravitropic responses reveals plants sum and subtract signals, (ii) the interplay between active growth-driven processes and passive mechanics.

In 2018, Keating, Rodgers, Roditty-Gershon and Rudnick conjectured that the variance of sums of the divisor
function in short intervals is described by a certain piecewise polynomial coming from a unitary matrix integral. That is
to say, this conjecture ties a straightforward arithmetic problem to random matrix theory. They supported their
conjecture by analogous results in the setting of polynomials over a finite field rather than in the integer setting. In this
talk, we'll discuss arithmetic problems over F_q[T] and their connections to matrix integrals, focusing on variations on
the divisor function problem with symplectic and orthogonal distributions. Joint work with Matilde Lalín.

In 2018, Keating, Rodgers, Roditty-Gershon and Rudnick conjectured that the variance of sums of the divisor function in short intervals is described by a certain piecewise polynomial coming from a unitary matrix integral. That is to say, this conjecture ties a straightforward arithmetic problem to random matrix theory. They supported their conjecture by analogous results in the setting of polynomials over a finite field rather than in the integer setting. In this talk, we'll discuss arithmetic problems over F_q[T] and their connections to matrix integrals, focusing on variations on the divisor function problem with symplectic and orthogonal distributions. Joint work with Matilde Lalín.

The triangle removal lemma of Ruzsa and Szemerédi is a fundamental result in extremal graph theory; very roughly speaking, it says that if a graph is "far" from triangle-free, then it contains "many" triangles. Despite decades of research, there is still a lot that we don't understand about this simple statement; for example, our understanding of the quantitative dependencies is very poor.

In this talk, I will discuss asymmetric versions of the triangle removal lemma, where in some cases we can get almost optimal quantitative bounds. The proofs use a mix of ideas coming from graph theory, number theory, probabilistic combinatorics, and Ramsey theory.

Based on joint work with Lior Gishboliner and Asaf Shapira.

Reconstructing continuous signals based on a small number of discrete samples is a fundamental problem across science and engineering. In practice, we are often interested in signals with ``simple'' Fourier structure -- e.g., those involving frequencies within a bounded range, a small number of frequencies, or a few blocks of frequencies. More broadly, any prior knowledge about a signal's Fourier power spectrum can constrain its complexity.  Intuitively, signals with more highly constrained Fourier structure require fewer samples to reconstruct.

We formalize this intuition by showing that, roughly speaking, a continuous signal from a given class can be approximately reconstructed using a number of samples equal to the statistical dimension of the allowed power spectrum of that class. We prove that, in nearly all settings, this natural measure tightly characterizes the sample complexity of signal reconstruction.

Surprisingly, we also show that, up to logarithmic factors, a universal non-uniform sampling strategy can achieve this optimal complexity for any class of signals. We present a simple, efficient, and general algorithm for recovering a signal from the samples taken. For bandlimited and sparse signals, our method matches the state-of-the-art. At the same time, it gives the first computationally and sample efficient solution to a broad range of problems, including multiband signal reconstruction and common kriging and Gaussian process regression tasks.

Our work is based on a novel connection between randomized linear algebra and the problem of reconstructing signals with constrained Fourier structure. We extend tools based on statistical leverage score sampling and column-based matrix reconstruction to the approximation of continuous linear operators that arise in the signal fitting problem. We believe that these extensions are of independent interest and serve as a foundation for tackling a broad range of continuous time problems using randomized methods.

This is joint work with Michael Kapralov, Cameron Musco, Christopher Musco, Ameya Velingker and Amir Zandieh

A link for this talk will be sent to our mailing list a day or two in advance.  If you are not on the list and wish to be sent a link, please send email to @email.

Abstract:

Quasicrystals have been observed recently in soft condensed mater, providing new insight into the ongoing quest to understand their formation and thermodynamic stability. I shall explain the stability of certain soft-matter quasicrystals, using surprisingly simple classical field theories, by making an analogy to Faraday waves. This will provide a recipe for designing pair potentials that yield crystals with (almost) any given symmetry.

We find the order of growth of the typical number of components of zero sets of smooth random functions of several real variables. This might be thought as a statistical version of the (first half of) 16th Hilbert problem. The primary examples are various ensembles of Gaussian real-valued polynomials (algebraic or trigonometric) of large degree, and smooth Gaussian functions on the Euclidean space with translation-invariant distribution.

Joint work with Fedor Nazarov.