• Apr 28 @ Penn: Ori Parzanchevski (IAS)

    Random walks, spectrum and homology

    There are intimate connections between the behavior of a random walk on a graph, and its topological and spectral properties. We define a stochastic process on higher dimensional simplicial complexes, which reflects their homological and spectral properties in a parallel way. This leads to high dimensional analogues and counter-analogues of classical theorems of Kesten, Alon-Boppana, and others.
    No previous knowledge is assumed. Joint work with Ron Rosenthal.

  • Apr 21 @ Temple: Alex Drewitz (Columbia)

    The maximal particle of branching random walk in random environment

    We consider one-dimensional branching random walk in a random branching environment and show that certain quantities related to the maximal particle fulfill a functional Central Limit Theorem. This is connected to fluctuations of the solutions to the parabolic Anderson model (i.e., the stochastic heat equation) as well as to a randomized version of the Fisher-KPP equation.

  • Apr 14 @ Penn: Milan Bradonjic (Bell Labs)

    Asymptotic laws for coloring sparse random geometric graphs with constant number of colors

    We study coloring of sparse random geometric graphs, in an arbitrary but constant dimension, with a constant number of colors. We show the law of large numbers, as well as the central limit theorem type results for the maximum number of nodes that can be properly colored. This object is neither scale-invariant nor smooth, so we design the tools that with the main method of subadditivity allow us to show the law of large numbers. Additionally, by proving the Lindeberg conditions, we show that the limiting distribution is Gaussian. For the constants that appear in these results, we provide the exact value in dimension one, and upper and lower bounds in higher dimensions. Joint work with Sem Borst.

  • Apr 7 @ Temple: Sean O'Rourke (Boulder)

    Singular values and vectors under random perturbation

    Computing the singular values and singular vectors of a large matrix is a basic task in high dimensional data analysis with many applications in computer science and statistics. In practice, however, data is often perturbed by noise. A natural question is the following. How much does a small perturbation to the matrix change the singular values and vectors?
    Classical (deterministic) theorems, such as those by Davis-Kahan, Wedin, and Weyl, give tight estimates for the worst-case scenario. In this talk, I will consider the case when the perturbation is random. In this setting, better estimates can be achieved when our matrix has low rank. This talk is based on joint work with Van Vu and Ke Wang.

  • Mar 31 @ Penn: Ted Hill (GATech)

    Fair-Division Problems

    The general subject of this talk is the question of whether an object (such as a cake or piece of land) can be divided among N people with possibly different values so that each person receives a fair portion. Formally, there are N values (measures) on the same object - a measurable space - and a typical goal is to partition the object into N (measurable) pieces, and assign each participant a piece that he himself values at least 1/N of the total. Classical fair-division includes Steinhaus's "Ham Sandwich Problem", Dubins and Spanier’s “Sliding Knife Algorithm”, Neyman and Pearson's "Bisection Problem", and Fisher's "Problem of the Nile". Generalizations of these, in both continuous and discrete measure settings, use tools such as Lyapounov's Convexity Theorem. The talk will include several open problems, and applications to disarmament, dividing inheritances, and selection of college deans or department chairs.

  • Mar 24 @ Penn: Govind Menon (Brown)

    The Hopf-Lax formula, integrability and commuting path transformations

    The study of partial differential equations with random data forms the basis of theories of turbulence and phase transitions. However, there are very few examples, where we have any real understanding of such ensembles.
    This talk is a description of the rich structure of one such problem: the analysis of perhaps a basic class of nonlinear PDE with random data (scalar conservation laws and Hamilton-Jacobi equations). I will rephrase our results on kinetic theory and PDE in terms of path transformations in order to connect with topics of current interest to probabilists and motivate a conjecture on path transformations that commute in law.

  • Mar 17 @ Penn: Ivan Corwin (Columbia)

    Stochastic quantum integrable systems

    We describe recent work involving interacting particle systems related to quantum integrable systems. This theory unites all known exactly solvable models in the Kardar-Parisi-Zhang universality class, as well as provides new examples of such systems, and new tools in their analysis.

  • Mar 10 @ Penn: Omer Tamuz (MIT)

    Majority Dynamics and the Period Two Property

    A group of people connected by a social network each start with some opinion in {0,1}. They then proceed to repeatedly update their opinions by conforming to those of the majority of their neighbors. On finite graphs, this model has the curious property that, when updates are synchronous, each person eventually either converges to a fixed opinion or else, from some point on, oscillates between the two possible opinions with period two. When updates are asynchronous each person's opinion converges. We will study this model on infinite graphs and random graphs, showing some old results, some new ones, and some nice open questions.
    Joint work with Ran Tessler.

  • Mar 3 @ CAGE: Greta Panova (Penn)

    Statistical mechanics via asymptotics of symmetric functions

    What do lozenge tilings (a.k.a. plane partitions, dimer covers of the hexagonal lattice), alternating sign matrices (or the 6-vertex model) and the dense loop model have in common? Besides the obvious, their limiting behavior can be studied with the help of some "asymptotic" algebraic combinatorics. We develop methods to analyze normalized symmetric functions (Schur functions and more general Lie group characters), as the indexing partition converges to a limiting profile. We apply this analysis together with some combinatorial interpretations to study the limiting behavior of the integrable models listed above. In particular, we show that the positions of horizontal lozenges near a vertical flat boundary are distributed like the eigenvalues of GUE matrices, and this holds for a wide class of domains (including such with free boundary). In the free boundary case we show that the corresponding height function (i.e. symmetric plane partition) converges to a limit shape. We discover Gaussian distribution for some observables of the Alternating Sign Matrices, leading again to GUE eigenvalues for the positions of 1s near the border (result of V. Gorin). We also find the asymptotics for the expected value of the mean total current between two adjacent points in the dense loop model.
    Based (mostly) on joint work with Vadim Gorin.

  • Feb 24 @ Penn: Jin Feng (Kansas)

    A rigorous approach to large time behavior of a 2-D vortex dynamics

    Onsager has a conjecture on large time behavior of vortex dynamics derived from Euler equation on 2D torus. For such argument to go through, at one point, one needs to invoke an (un-available) ergodic theory for deterministic Hamiltonian systems.
    Relaxing to stochastic vortex dynamics (corresponding to mean-field models of 2D Navier-Stokes) instead, one can add another parameter. By considering an re-arranged multi-parameter limit, one can reformulate the problem as a combination of large deviation problem, and large time behavior for quasi-potentials in space of probability measures. This talk will focus on a theory of Hamilton-Jacobi equation in space of probability measures developed for solving both the above problems.
    Talk will be based on joint works with Andrzej Swiech.

  • Feb 17 @ Penn: Doron Puder (IAS)

    Primitive Words, Measure Preservation and Fixed points in Random Permutations

    We establish a new characterization of primitive elements in free groups, which is based on the distributions they induce on finite groups.
    More specifically, for every finite group G, a word w in the free group on k generators defines a word map from G^k to G. We say that w is measure preserving with respect to G if given uniform distribution on G^k, the image of this word map distributes uniformly on G. It is easy to see that primitive words (words which belong to some free generating set of the free group) are measure preserving w.r.t. all finite groups, and several authors have conjectured that the two properties are, in fact, equivalent. In a joint work with O. Parzanchevski, we prove this conjecture. The proof is based on the average number of fixed points in a random permutation distributed according to w. All notions will be defined during the talk.

  • Feb 10 @ Temple: Benedek Valko (UW-Madison)

    Operator limits of random matrices

    By the Hilbert-Polya conjecture the critical zeros of the Riemann zeta function correspond to the eigenvalues of a self adjoint operator. By a conjecture of Dyson and Montgomery the critical zeros (after a certain rescaling) look like the bulk eigenvalue limit point process of the Gaussian Unitary Ensemble. It is natural to ask if this point process can be described as the spectrum of a random self adjoint operator. We show that this is indeed the case: in fact for any beta>0 the bulk limit of the Gaussian beta ensemble can be obtained as the spectrum of a self adjoint random differential operator.
    (Joint with Balint Virag)

  • Jan 20 @ Penn: Dieter Mitsche (Nice)

    On rigidity, orientability and cores of random graphs with sliders

    Suppose that you add rigid bars between points in the plane, and suppose that a constant fraction q of the points moves freely in the whole plane; the remaining fraction is constrained to move on fixed lines called sliders. When does a giant rigid cluster emerge? Under a genericity condition, the answer only depends on the graph formed by the points (vertices) and the bars (edges). We find for the random graph G(n,c/n) the threshold value of c for the appearance of a linear-sized rigid component as a function of q, generalizing results of Kasiviswanathan et al. We show that this appearance of a giant component undergoes a continuous transition for q <= 1/2 and a discontinuous transition for q > 1/2. In our proofs, we introduce a generalized notion of orientability interpolating between 1- and 2-orientability, of cores interpolating between the 2-core and the 3-core, and of extended cores interpolating between the 2+1-core and the 3+2-core; we find the precise expressions for the respective thresholds and the sizes of the different cores above the threshold. In particular, this proves a conjecture of Kawiviswanathan et al. about the size of the 3+2-core. We also derive some structural properties of rigidity with sliders (matroid and decomposition into components) which can be of independent interest.
    Joint work with Julien Barré and Marc Lelarge.

  • Dec 9 @ Penn: Will Perkins (IMA, Birmingham)

    Algorithmically Partitioning Random Hypergraphs

    I will discuss the problem of finding a planted bipartition in a random k-uniform hypergraph (the hypergraph version of the stochastic block model). The problem exhibits an algorithmic gap: while the partition is detectable with a linear number of hyperedges, the best known efficient algorithms require up to n^{k/2} hyperedges. I'll present a general framework for proving computational lower bounds for the class of statistical algorithms on problems over distributions and apply it to the planted partition problem to achieve nearly matching upper and lower bounds. Based on joint work with Vitaly Feldman and Santosh Vempala.

  • Nov 18 @ Temple: Louis-Pierre Arguin (CUNY)

    Probabilistic approach for the maxima of the Riemann Zeta function on the critical line

    A recent conjecture of Fyodorov, Hiary & Keating states that the maxima of the Riemann Zeta function on a bounded interval of the critical line behave similarly to the maxima of a specific class of Gaussian fields, the so-called log-correlated Gaussian fields. These include important examples such as branching Brownian motion and the 2D Gaussian free field. In this talk, we will highlight the connections between the number theory problem and the probabilistic models. We will outline the proof of the conjecture in the case of a randomized model of the Zeta function. We will discuss possible approaches to the problem for the function itself.
    This is joint work with D. Belius (NYU) and A. Harper (Cambridge).

  • Oct 28 @ Temple: Mykhaylo Shkolnikov (Princeton)

    Intertwinings, wave equations and beta ensembles

    We will discuss a general theory of intertwined diffusion processes of any dimension. Intertwined processes arise in many different contexts in probability theory, most notably in the study of random matrices, random polymers and path decompositions of Brownian motion. Recently, they turned out to be also closely related to wave equations and more general hyperbolic partial differential equations. The talk will be devoted to this recent development, as well as an algebraic perspective on intertwinings which, in particular, gives rise to a novel intertwining in beta random matrix theory. The talk is based on joint works with Vadim Gorin and Soumik Pal.

  • Oct 21 @ Temple: Noga Alon (Tel Aviv and IAS)

    Bipartite Decomposition of (random) Graphs

    For a graph G, let bc(G) denote the minimum possible number of pairwise edge disjoint complete bipartite subgraphs of G so that each edge of G belongs to (exactly) one of them. The study of this quantity and its variants received a considerable amount of attention and is related to problems in communication complexity and geometry. After a brief discussion of the background and earlier results on the subject I will focus on the problem of determining the typical value of bc(G) for the binomial random graph G=G(n,p), showing that a conjecture of Erdos about it is false, and suggesting a modified version. Partly based on joint work with Tom Bohman and Hao Huang.

  • Oct 14 @ Penn: Jonathan Mattingly (Duke)

    What is an elliptic stochastic partial differential equation anyway?

    I will discuss how much randomness one needs for the infinite dimensional diffusion associated an stochastic partial differential equation (SPDE) to be ``elliptic''. Along the way I will consider hypoeelipticity for SPDEs. Most of the discussion will be framed in terms of the ergodic or long time behavior of the systems. I will talk about some concrete examples such and the Navier-Stokes equations and Reaction Diffusion Equations.

  • Oct 7 @ Penn: Nick Wormald (Monash)

    On the diameter and longest paths in random Apollonian networks

    Start with a triangle embedded in the plane. In each step, choose a bounded face uniformly at random, add a vertex inside that face and join it to the vertices of the face. After $n-3$ steps, we obtain a random triangulated plane graph with $n$ vertices, which is called a random Apollonian network. Asymptotically almost surely, the diameter of the resulting network is is asymptotic to $c \log n$, where $c\approx 1.668$, and the longest path length is at most $n^\delta$ for some $\delta<1$.
    The latter result refutes a conjecture of Frieze and Tsourakakis, and confirms a conjecture of Cooper and Frieze. For its proof, we bound the size of the largest regular ($r$-ary) subtrees of the random recursive tree with $t$ vertices.
    Includes joint work with Andrea Collevecchio, Ehsan Ebrahimzadeh, Linda Farczadi, Pu Gao, Abbas Mehrabian, Cristiane M. Sato, Jonathan Zung.

  • Sep 30 @ Penn: Allan Sly (Berkeley)

    Increasing subsequences on the plane and the Slow bond conjecture

    For a Poisson process in R^2 with intensity 1, the distribution of the maximum number of points on an oriented path from (0,0) to (N,N) has been studied in detail, culminating in Baik-Deift-Johansson's celebrated Tracy-Widom fluctuation result. We consider a variant of the model where one adds, on the diagonal, additional points according to an independent one dimensional Poisson process with rate \lambda. The question of interest here is whether for all positive values of \lambda, this results in a change in the law of large numbers for the the number of points in the maximal path. A closely related question comes from a variant of Totally Asymmetric Exclusion Process, introduced by Janowsky and Lebowitz. Consider a TASEP in 1-dimension, where the bond at the origin rings at a slower rate r<1. The question is whether for all values of r<1, the single slow bond produces a macroscopic change in the system. We provide affirmative answers to both questions.
    Based on joint work with Riddhipratim Basu and Vladas Sidoravicius

  • Sep 22 (Monday) @ Temple Colloquium: Mark Rudelson (Michigan)

    Non-Asymptotic Approach in Random Matrix Theory

    Random matrix theory studies the asymptotics of the spectral distributions of families of random matrices, as the sizes of the matrices tend to infinity. Derivation such asymptotics frequently requires analyzing the spectral properties of random matrices of a large fixed size, especially of their singular values. We will discuss several recent results in this area concerning matrices with independent entries, as well as random unitary and orthogonal perturbations of a fixed matrix. We will also show an application of the non-asymptotic random matrix theory to estimating the permanent of a deterministic matrix.

  • Sep 16 @ CAGE: Igor Pak (UCLA)

    Counting irrational tilings

    Counting tilings of a rectangle is a classical problem going back to the beginning of Enumerative Combinatorics. In 1961, Schützenberger gave characterizations of the resulting g.f.´s in terms of certain operations, and a complete solution was found by Berstel and Soittola in 1970s. I will review these results and then present a generalization to irrational tilings we recently found with Garrabrant. These turn out to be connected to positive binomial multisums. I will conclude with some open problems on Catalan numbers and asymptotics, among other things.

  • Sep 9 @ Penn: Brett Hemenway (Penn CIS)

    Locally Correctable Codes and Expander Graphs

    An error-correcting code is called locally decodable if there exists a decoding algorithm that can recover any symbol of the message with high probability by reading only a small number of symbols of the corrupted codeword.
    There is a fundamental tradeoff in locally decodable codes between the rate (the ratio of message length to codeword length) and the locality (the number of symbols read by the decoder). Ideally, one strives for high rate and low locality. Constructions of locally decodable codes can be divided into two categories, low-rate, low-locality and high-rate, high-locality. The Matching Vector codes of Yekhanin and Efremenko have locality 3, but their rate goes to zero super-polynomially. The Multiplicity Codes of Kopparty, Saraf and Yekhanin and the Affine Invariant Codes of Guo, Kopparty and Sudan have high rate (approaching one) and locality $n^\epsilon$.
    In this work we provide a local-decoding algorithm for the expander codes of Sipser and Spielman. When appropriately instantiated, this leads to a novel construction of locally decodable codes with rate approaching one and locality $n^\epsilon$.
    This work appeared in ICALP '13 and is joint work with Rafail Ostrovsky and Mary Wootters. http://arxiv.org/abs/1304.8129