- You are here:
- GT Home
- Home
- News & Events

Series: Stochastics Seminar

Series: Stochastics Seminar

Series: Stochastics Seminar

Series: Stochastics Seminar

Series: Stochastics Seminar

Series: Stochastics Seminar

We discuss two recent results concerning disease modeling on networks. The infection is assumed to spread via contagion (e.g., transmission over the edges of an underlying network). In the first scenario, we observe the infection status of individuals at a particular time instance and the goal is to identify a confidence set of nodes that contain the source of the infection with high probability. We show that when the underlying graph is a tree with certain regularity properties and the structure of the graph is known, confidence sets may be constructed with cardinality independent of the size of the infection set. In the scenario, the goal is to infer the network structure of the underlying graph based on knowledge of the infected individuals. We develop a hypothesis test based on permutation testing, and describe a sufficient condition for the validity of the hypothesis test based on automorphism groups of the graphs involved in the hypothesis test. This is joint work with Justin Khim (UPenn).

Series: Stochastics Seminar

We consider rooted subgraph
extension counts, such as (a) the number of triangles containinga given vertex, or (b) the number of paths of length three connecting two
given vertices.
In 1989 Spencer gave sufficient conditions for the event that whp all
roots of the binomial random graph G(n,p) have the same asymptotic
number of extensions, i.e., (1 \pm \epsilon) times their expected
number.
Perhaps surprisingly, the question whether these conditions are
necessary has remained open. In this talk we briefly discuss our
qualitative solution of this problem for the `strictly balanced' case,
and mention several intriguing questions that remain open (which lie at the intersection of probability theory + discrete mathematics, and are of concentration inequality type).
Based on joint work in progress with Matas Sileikis

Series: Stochastics Seminar

I will revisit the classical Stein's method, for normal random variables, as well as its version for Poisson random variables and show how both (as well as many other examples) can be incorporated in a single framework.

Series: Stochastics Seminar

We discuss scaling methods
which can be used to solve low mode control problems for nonlinear
partial differential equations. These methods lead naturally to a
infinite-dimensional generalization of the notion of saturation,
originally due to Jurdjevic and Kupka in the finite-dimensional setting
of ODEs. The methods will be highlighted by applying them to specific
equations, including reaction-diffusion equations, the 2d/3d
Euler/Navier-Stokes equations and the 2d Boussinesq equations.
Applications to support properties of the laws solving randomly-forced
versions of each of these equations will be noted.

Series: Stochastics Seminar

Spectral algorithms are a powerful method for detecting low-rank structure
in dense random matrices and random graphs. However, in certain problems
involving sparse random graphs with bounded average vertex degree, a naive
spectral analysis of the graph adjacency matrix fails to detect this
structure. In this talk, I will discuss a semidefinite programming (SDP)
approach to address this problem, which may be viewed both as imposing a
delocalization constraint on the maximum eigenvalue problem and as a
natural convex relaxation of minimum graph bisection. I will discuss
probabilistic results that bound the value of this SDP for sparse
Erdos-Renyi random graphs with fixed average vertex degree, as well as an
extension of the lower bound to the two-group stochastic block model. Our
upper bound uses a dual witness construction that is related to the
non-backtracking matrix of the graph. Our lower bounds analyze the behavior
of local algorithms, and in particular imply that such algorithms can
approximately solve the SDP in the Erdos-Renyi setting.
This is joint work with Andrea Montanari.