Shirshendu Ganguly

Shirshendu Ganguly


I am currently a Miller Fellow in Statistics and Mathematics at UC Berkeley. I got my PhD in Mathematics from University of Washington in Spring 2016 where I was advised by Ioana Dumitriu and Christopher Hoffman . Prior to this, I obtained bachelors and masters in Statistics from Indian Statistical Institute, Kolkata.

Me

Research

I am broadly interested in probability theory and its applications. Recently I have been working on problems in markov chains related to spin systems, random walk on graphs, Gibbs measure on random matrices, geometry of geodesics in percolation, and large deviation theory in sparse combinatorial settings, etc. I am also interested in applications of information theory to understand high dimensional phenomena.

A complete list of publications and preprints is given here. Here is my CV.

Research Internships

  • Microsoft Research, Redmond: Summer, 2013. Mentored by Eyal Lubetzky and Yuval Peres.
  • Microsoft Research, NE: Summer, 2014. Mentored by Christian Borgs.
  • Microsoft Research, Redmond: Summer, 2015. Mentored by Sebastien Bubeck.
  • Some Recent Works

    Geometry of constrained polymers

    The Competition of Roughness and Curvature in Area-Constrained Polymer Models (with Riddhipratim Basu, Alan Hammond) Arxiv

    The competition between local Brownian roughness and global parabolic curvature experienced in many random interface models reflects an important aspect of the KPZ universality class. It may be summarised by an exponent triple (1/2,1/3,2/3) representing local interface fluctuation, local roughness (or inward deviation) and convex hull facet length. The three effects arise, for example, in droplets in planar Ising models (Alexander, '01, Hammond, '11,'12). In this article, we offer a new perspective on this phenomenon. We consider directed last passage percolation model in the plane, a paradigmatic example in the KPZ universality class, and constrain the maximizing path under the additional requirement of enclosing an atypically large area. The interface suffers a constraint of parabolic curvature as before, but now its local structure is the KPZ fixed point polymer's rather than Brownian. The local interface fluctuation exponent is thus two-thirds rather than one-half. We prove that the facet lengths of the constrained path's convex hull are governed by an exponent of 3/4, and inward deviation by an exponent of 1/2. That is, the exponent triple is now (2/3,1/2,3/4) in place of (1/2,1/3,2/3). This phenomenon appears to be shared among various isoperimetrically extremal circuits in local randomness. Indeed, we formulate a conjecture to this effect concerning such circuits in supercritical percolation, whose Wulff-like first-order behaviour was recently established (Biskup, Louidor, Procaccia and Rosenthal, '12)

    Mixing time of random walk on matrices.

    Upper triangular matrix walk: cutoff for finitely many columns. (with Fabio Martinelli) Arxiv

    We consider random walk on the group of uni-upper triangular matrices with entries in F_2 which forms an important example of a nilpotent group. Peres and Sly (2013) proved tight bounds on the mixing time of this walk up to constants. It is well known that the single column projection of this chain is the one dimensional East process. In this article, we complement the Peres-Sly result by proving a cutoff result for the mixing of finitely many columns in the upper triangular matrix walk at the same location as the East process of the same dimension. Moreover, we also show that the spectral gaps of the matrix walk and the East process are equal. The proof of the cutoff result is based on a recursive argument which uses a local version of a dual process appearing in Peres and Sly (2013), various combinatorial consequences of mixing and concentration results for the movement of the front in the one dimensional East process.

    Escape rates of Random walk on stationary graphs.

    Diffusive estimates for random walks on stationary random graphs of polynomial growth. (with James R. Lee, Yuval Peres) To appear in GAFA (2017) Arxiv

    We show that for any stationary random graph (G,p) of annealed polynomial growth there is an infinite sequence of times {t_n} at which the random walk {X_t} on (G,p) is at most diffusive. This result is new even in the case when G is a stationary random subgraph of Z^d. Combined with the work of Benjamini, Duminil-Copin, Kozma, and Yadin (2015), it implies that G almost surely does not admit a non-constant harmonic function of sublinear growth. To complement this, we argue that passing to a subsequence of times {t_n} is necessary, as there are stationary random graphs of (almost sure) polynomial growth where the random walk is almost surely superdiffusive at an infinite subset of times.

    Gibbs measure on Random Matrices and Lattice gauge theory.

    SO(N) Lattice Gauge Theory, Planar and Beyond (with Riddhipratim Basu) To appear in Communications on Pure and Applied Mathematics (2017). Arxiv

    Lattice Gauge theories have been studied in the physics literature as discrete approximations to quantum Yang-Mills theory for a long time. Primary statistics of interest in these models are expectations of the so called “Wilson loop variables”. In this article we continue the program initiated by Chatterjee (2015) to understand Wilson loop expectations in Lattice Gauge theories in a certain limit through gauge-string duality. The objective in this paper is to better understand the underlying combinatorics in the strong coupling regime, by giving a more geometric picture of string trajectories involving correspondence to objects such as decorated trees and non-crossing partitions. Using connections with Free Probability theory, we provide an elaborate description of loop expectations in the the planar setting, which provides certain insights about structures of higher dimensional trajectories as well. Exploiting this, we construct a counter example showing that in any dimension, the Wilson loop area law lower bound does not hold in full generality, and thereby partially answer a question from Chatterjee (2015) in the negative.

    Competitive Erosion

    Interface formation by Competitive Erosion (with Lionel Levine, Yuval Peres and James Propp) To appear in PTRF (2016) Arxiv
    Competitive erosion is conformally invariant (with Yuval Peres) Arxiv

    We study a graph-theoretic model of interface dynamics called Competitive Erosion. Each vertex of the graph is occupied by a particle, which can be either red or blue. New red and blue particles are emitted alternately from their respective bases and perform random walk. On encountering a particle of the opposite color they remove it and occupy its position. Based on conformally invariant nature of reflected brownian motion Propp conjectured in 2003 that at stationarity, with high probability the blue and the red regions are separated by an orthogonal circular arc on the disc and by a suitable hyperbolic geodesic on a general simply connected domain. In the first article we study Competitive Erosion on the cylinder graph which has a relatively simple geometry.
    In the second article we confirm Propp's prediction on smooth enough planar simply connected domains.
    Competitive erosion started from a random coloring spontaneously forms an interface.

    Large deviation and counting problems in sparse settings.

    Upper tails and independence polynomials in random graphs (with Bhaswar B. Bhattacharya, Eyal Lubetzky, Yufei Zhao). To appear in Advances in Mathematics (2017). Arxiv
    Upper tails for arithmetic progressions in a random set (with with Bhaswar B. Bhattacharya, Xuancheng Shao, Yufei Zhao) Arxiv

    The upper tail problem in the Erdos-Renyi random graph G∼G(n,p) asks to estimate the probability that the number of copies of a graph H in G exceeds its expectation by a factor 1+δ. Chatterjee and Dembo (2014) showed that in the sparse regime of p→0 as n→∞ with p bigger than an inverse power of n, this problem reduces to a natural variational problem on weighted graphs, which was thereafter asymptotically solved by two of the authors in the case where H is a clique. Here we extend the latter work to any fixed graph H and determine a function cH(δ) such that, for p as above and any fixed δ >0, the logarithm of the upper tail probability properly normalized converges to cH(δ). As it turns out, the leading order constant in the large deviation rate function, cH(δ), is governed by the independence polynomial of H.

    The second article investigates similar questions in the setting of counting arithmetic progressions in random subsets of Z/nZ. For progressions of length greater than three, a new large deviation principle is established using the arithmetic regularity lemma based on the powerful machinery of inverse theorem for Gowers norms.

    Self organized criticality

    Non-fixation for conservative stochastic dynamics on the line (with Riddhipratim Basu, Christopher Hoffman). Arxiv

    We consider Activated Random Walk (ARW), a model which generalizes the Stochastic Sandpile, one of the canonical examples of self organized criticality. Informally ARW is a particle system on Z, with initial mass density μ > 0 of active particles. Active particles do a symmetric random walk at rate one and fall asleep at rate λ > 0. Sleepy particles become active on coming in contact with other active particles. We investigate the question of fixation/non-fixation of the process and show for small enough λ the critical mass density for fixation is strictly less than one. Moreover, the critical density goes to zero as λ tends to zero. This positively answers two open questions from Dickman, Rolla, Sidoravicius (J. Stat. Phys., 2010) and Rolla, Sidoravicius (Invent. Math., 2012).

    East Process

    Cutoff for the East Process (with Eyal Lubetzky and Fabio Martinelli) Communications in Mathematical Physics (2015). Arxiv

    The East process is a 1D kinetically constrained interacting particle system, introduced in the physics literature in the early 90's to model liquid-glass transitions. Spectral gap estimates of Aldous and Diaconis in 2002 imply that its mixing time on L sites has order L. We complement that result and show cutoff with an O(√L)-window. The main ingredient is an analysis of the front of the process (its rightmost zero in the setup where zeros facilitate updates to their right). One expects the front to advance as a biased random walk, whose normal fluctuations would imply cutoff with an O(√L)-window. The law of the process behind the front plays a crucial role: Blondel showed that it converges to an invariant measure ν, on which very little is known. Here we obtain quantitative bounds on the speed of convergence to ν, finding that it is exponentially fast. We then derive that the increments of the front behave as a stationary mixing sequence of random variables, and a Stein-method based argument of Bolthausen ('82) implies a CLT for the location of the front, yielding the cutoff result. Finally, we supplement these results by a study of analogous kinetically constrained models on trees, again establishing cutoff, yet this time with an O(1)-window.

    Markov chain on graphs and Universality of spectral fluctuations

    The Random Transposition Dynamics on Random Regular Graphs and the Gaussian Free Field (with Soumik Pal) Arxiv

    A single permutation, seen as a union of disjoint cycles, represents a regular graph of degree two. Consider d many independent random permutations and superimpose their graph structures. It is a common model of a random regular (multi-) graph of degree 2d. We consider the following dynamics. The dimension (i.e. size) of each permutation grows by coupled Chinese Restaurant Processes, while in time each permutation evolves according to the random transposition chain. Asymptotically in the size of the graph one observes a remarkable evolution of short cycles and linear eigenvalue statistics in dimension and time. In dimension, it was shown by Johnson and Pal (2014) that cycle counts are described by a Poisson field of Yule processes. Here, we give a Poisson random surface description in dimension and time of the limiting cycle counts for every d. As d grows to infinity, the fluctuation of the limiting cycle counts, across dimension, converges to the Gaussian Free Field. In time this field is preserved by a stationary Gaussian dynamics. The laws of these processes are similar to eigenvalue fluctuations of the minor process of a real symmetric Wigner matrix whose coordinates evolve as i.i.d. stationary stochastic processes.

    Oil and Water Model

    Oil and water: a two-type internal aggregation model (with Elisabetta Candellero, Christopher Hoffman and Lionel Levine) Annals of Probability Arxiv

    We introduce a two-type internal DLA model which is an example of a non-unary abelian network. Starting with n "oil" and n "water" particles at the origin, the particles diffuse in Z according to the following rule: whenever some site x has at least 1 oil and at least 1 water particle present, it "fires" by sending 1 oil particle and 1 water particle each to an independent random neighbor x+1 or x-1. Firing continues until every site has at most one type of particles. We establish the correct order for several statistics of this model. In particular we show that the "odometer function" scales like n^{4/3}. We also identify the scaling limit under assumption of existence.


    The first figure shows the "odometer" function and the red and blue bars show the pile of particles of each type at easch site.
    The second figure shows the set of occupied sites on the two dimensional lattice.

    Rotor Walks

    Escape rates for rotor walks on Z^d (with Laura Florescu, Lionel Levine and Yuval Peres).
    SIAM Journal on Discrete Mathematics (2014) Arxiv

    Rotor walk is a deterministic analogue of random walk. We study its recurrence and transience properties on Z^d for the initial configuration of all rotors aligned.
    If n particles in turn perform rotor walks starting from the origin, we show that the number that escape (i.e., never return to the origin) is of order n in dimensions
    d ≥ 3, and of order n/ log n in dimension 2.
    Different colors represent the directions in which rotors point after 800 particles starting from the origin have exited a square of size 200.

    Coauthors

    Riddhipratim Basu , Christian Borgs , Arup Bose , Bhaswar Bhattacharya , Gerandy Brito, Sébastien Bubeck , Elisabetta Candellero , Jennifer. T. Chayes , Henry Cohn , Sayantan Das, Ioana Dumitriu , Laura Florescu , Rajat Subhra Hazra , Christopher Hoffman , James R. Lee , Lionel Levine , Eyal Lubetzky , Subhamoy Maitra , Fabio Martinelli , Soumik Pal , Goutam Paul, Yuval Peres , James Propp , Fernando Xuancheng Shao , Joel Spencer , Yufei Zhao .

    Teaching

    I have been a teaching assistant for undergraduate calculus courses in Fall 2011, Winter, Spring 2012, and Winter 2015 at UW. I have also been a grader for Graduate Complex Analysis in Fall, Winter 2013.

    Contact

    307, Evans Hall,
    Department of Statistics,
    University of California, Berkeley,
    CA, 94720.
    Email: sganguly@berkeley.edu,
    sganguly@math.washington.edu.