# Difference between revisions of "Probability Seminar"

(→Thursday, 4/20/2017, Jinsu Kim, UW-Madison) |
(→Thursday, April 26, 2018, Philip Matchett Wood, UW-Madison) |
||

(80 intermediate revisions by 2 users not shown) | |||

Line 1: | Line 1: | ||

__NOTOC__ | __NOTOC__ | ||

− | = Spring | + | = Spring 2018 = |

<b>Thursdays in 901 Van Vleck Hall at 2:25 PM</b>, unless otherwise noted. | <b>Thursdays in 901 Van Vleck Hall at 2:25 PM</b>, unless otherwise noted. | ||

Line 8: | Line 8: | ||

If you would like to sign up for the email list to receive seminar announcements then please send an email to join-probsem@lists.wisc.edu. | If you would like to sign up for the email list to receive seminar announcements then please send an email to join-probsem@lists.wisc.edu. | ||

− | <!-- == | + | <!-- == Thursday, January 25, 2018, TBA== --> |

+ | == Thursday, February 1, 2018, [https://people.math.osu.edu/nguyen.1261/ Hoi Nguyen], [https://math.osu.edu/ OSU]== | ||

− | + | Title: '''A remark on long-range repulsion in spectrum''' | |

− | + | Abstract: In this talk we will address a "long-range" type repulsion among the singular values of random iid matrices, as well as among the eigenvalues of random Wigner matrices. We show evidence of repulsion under arbitrary perturbation even in matrices of discrete entry distributions. In many cases our method yields nearly optimal bounds. | |

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | Abstract: | ||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | == Thursday, | + | == Thursday, February 8, 2018, [http://www.math.purdue.edu/~peterson/ Jon Peterson], [http://www.math.purdue.edu/ Purdue] == |

+ | Title: '''Quantitative CLTs for random walks in random environments''' | ||

− | + | Abstract:The classical central limit theorem (CLT) states that for sums of a large number of i.i.d. random variables with finite variance, the distribution of the rescaled sum is approximately Gaussian. However, the statement of the central limit theorem doesn't give any quantitative error estimates for this approximation. Under slightly stronger moment assumptions, quantitative bounds for the CLT are given by the Berry-Esseen estimates. In this talk we will consider similar questions for CLTs for random walks in random environments (RWRE). That is, for certain models of RWRE it is known that the position of the random walk has a Gaussian limiting distribution, and we obtain quantitative error estimates on the rate of convergence to the Gaussian distribution for such RWRE. This talk is based on joint works with Sungwon Ahn and Xiaoqin Guo. | |

− | |||

− | |||

− | + | == <span style="color:red"> Friday, 4pm </span> February 9, 2018, <span style="color:red">Van Vleck B239</span> [http://www.math.cmu.edu/~wes/ Wes Pegden], [http://www.math.cmu.edu/ CMU]== | |

− | |||

− | <div style="width: | + | <div style="width:400px;height:75px;border:5px solid black"> |

− | <b><span style="color:red"> Please note the unusual day and time </span></b> | + | <b><span style="color:red"> This is a probability-related colloquium---Please note the unusual room, day, and time! </span></b> |

</div> | </div> | ||

− | + | Title: '''The fractal nature of the Abelian Sandpile''' | |

− | |||

− | Title: ''' | ||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | + | Abstract: The Abelian Sandpile is a simple diffusion process on the integer lattice, in which configurations of chips disperse according to a simple rule: when a vertex has at least 4 chips, it can distribute one chip to each neighbor. | |

+ | Introduced in the statistical physics community in the 1980s, the Abelian sandpile exhibits striking fractal behavior which long resisted rigorous mathematical analysis (or even a plausible explanation). We now have a relatively robust mathematical understanding of this fractal nature of the sandpile, which involves surprising connections between integer superharmonic functions on the lattice, discrete tilings of the plane, and Apollonian circle packings. In this talk, we will survey our work in this area, and discuss avenues of current and future research. | ||

− | + | == Thursday, February 15, 2018, Benedek Valkó, UW-Madison == | |

− | + | Title: '''Random matrices, operators and analytic functions''' | |

− | + | Abstract: Many of the important results of random matrix theory deal with limits of the eigenvalues of certain random matrix ensembles. In this talk I review some recent results on limits of `higher level objects' related to random matrices: the limits of random matrices viewed as operators and also limits of the corresponding characteristic functions. | |

− | |||

− | |||

− | Abstract: | ||

− | |||

− | + | Joint with B. Virág (Toronto/Budapest). | |

− | + | == Thursday, February 22, 2018, [http://pages.cs.wisc.edu/~raskutti/ Garvesh Raskutti] [https://www.stat.wisc.edu/ UW-Madison Stats] and [https://wid.wisc.edu/people/garvesh-raskutti/ WID]== | |

+ | Title: '''Estimation of large-scale time series network models''' | ||

Abstract: | Abstract: | ||

+ | Estimating networks from multi-variate time series data | ||

+ | is an important problem that arises in many applications including | ||

+ | computational neuroscience, social network analysis, and many | ||

+ | others. Prior approaches either do not scale to multiple time series | ||

+ | or rely on very restrictive parametric assumptions in order to | ||

+ | guarantee mixing. In this talk, I present two approaches that provide | ||

+ | learning guarantees for large-scale multi-variate time series. The first | ||

+ | involves a parametric GLM framework where non-linear clipping and | ||

+ | saturation effects that guarantee mixing. The second involves a | ||

+ | non-parametric sparse additive model framework where beta-mixing | ||

+ | conditions are considered. Learning guarantees are provided in both | ||

+ | cases and theoretical results are supported both by simulation results | ||

+ | and performance comparisons on various data examples. | ||

+ | <!-- == Thursday, March 1, 2018, TBA== --> | ||

− | + | == Thursday, March 8, 2018, [http://www.math.cmu.edu/~eemrah/ Elnur Emrah], [http://www.math.cmu.edu/index.php CMU] == | |

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | + | Title: '''Busemann limits for a corner growth model with deterministic inhomogeneity''' | |

− | Title: | ||

Abstract: | Abstract: | ||

− | + | Busemann limits have become a useful tool in study of geodesics in percolation models. The | |

− | + | properties of these limits are closely related to the curvature of the limit shapes in the associated | |

− | + | growth models. In this talk, we will consider a corner growth model (CGM) with independent | |

− | + | exponential weights. The rates of the exponentials are deterministic and inhomogeneous across | |

− | + | columns and rows. (An equivalent model is the TASEP with step initial condition and with | |

− | + | particlewise and holewise deterministic disorder). In particular, the model lacks stationarity. | |

− | + | Under mild assumptions on the rates, the limit shape in our CGM exists, is concave and can | |

− | + | develop flat regions only near the axes. In contrast, flat regions can only occur away from the axes | |

− | + | in the CGM with general i.i.d. weights. This feature and stationarity have been instrumental in | |

− | + | proving the existence of the Busemann limits in past work. We will discuss how to adapt and | |

− | + | extend these arguments to establish the existence and main properties of the Busemann limits | |

− | + | in both flat and strictly concave regions for our CGM. The results we will present are from an | |

− | + | ongoing joint project with Chris Janjigian and Timo Seppäläinen. | |

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | + | == Thursday, March 15, 2018, [http://web.mst.edu/~huwen/ Wenqing Hu] [http://math.mst.edu/ Missouri S&T]== | |

− | Title: ''' | + | Title: '''A random perturbation approach to some stochastic approximation algorithms in optimization''' |

− | Abstract: | + | Abstract: Many large-scale learning problems in modern statistics and machine learning can be reduced to solving stochastic optimization problems, i.e., the search for (local) minimum points of the expectation of an objective random function (loss function). These optimization problems are usually solved by certain stochastic approximation algorithms, which are recursive update rules with random inputs in each iteration. In this talk, we will be considering various types of such stochastic approximation algorithms, including the stochastic gradient descent, the stochastic composite gradient descent, as well as the stochastic heavy-ball method. By introducing approximating diffusion processes to the discrete recursive schemes, we will analyze the convergence of the diffusion limits to these algorithms via delicate techniques in stochastic analysis and asymptotic methods, in particular random perturbations of dynamical systems. This talk is based on a series of joint works with Chris Junchi Li (Princeton), Weijie Su (UPenn) and Haoyi Xiong (Missouri S&T). |

+ | == Thursday, March 22, 2018, [http://math.mit.edu/~mustazee/ Mustazee Rahman], [http://math.mit.edu/index.php MIT]== | ||

− | + | Title: On shocks in the TASEP | |

− | + | Abstract: The TASEP particle system, moving rightward, runs into traffic jams when the initial particle density to the left of the origin is smaller than the density to the right. The density function satisfies Burgers' equation and traffic jams correspond to its shocks. I will describe work with Jeremy Quastel on a specialization of the TASEP where we identify joint fluctuations of particles at the shock by using determinantal formulae for correlation functions of TASEP and its KPZ scaling limit. The limit process is expressed in terms of GOE Tracy-Widom laws. | |

− | + | This video shows the shock forming in Burgers' equation: https://www.youtube.com/watch?v=d49agpI0vu4 | |

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | == Thursday, | + | == Thursday, March 29, 2018, Spring Break == |

+ | == Thursday, April 5, 2018, [http://www.math.wisc.edu/~qinli/ Qin Li], [http://www.math.wisc.edu/ UW-Madison] == | ||

− | Title: ''' | + | Title: '''PDE compression — asymptotic preserving, numerical homogenization and randomized solvers''' |

Abstract: | Abstract: | ||

− | + | All classical PDE numerical solvers are deterministic. Grids are sampled and basis functions are chosen a priori. The corresponding discrete operators are then inverted for the numerical solutions. | |

− | + | We study if randomized solvers could be used to compute PDEs. More specifically, for PDEs that demonstrate multiple scales, we study if the macroscopic behavior in the solution could be quickly captured via random sampling. The framework we build is general and it compresses PDE solution spaces with no analytical PDE knowledge required. The concept, when applied onto kinetic equations and elliptic equations with porous media, is equivalent to asymptotic preserving and numerical homogenization respectively. | |

− | == Thursday, | + | == Thursday, April 12, 2018, [http://www.math.wisc.edu/~roch/ Sebastien Roch], [http://www.math.wisc.edu/ UW-Madison]== |

− | |||

− | + | Title: '''Circular Networks from Distorted Metrics''' | |

− | |||

− | + | Abstract: Trees have long been used as a graphical representation of species relationships. However | |

+ | complex evolutionary events, such as genetic reassortments or hybrid speciations which | ||

+ | occur commonly in viruses, bacteria and plants, do not fit into this elementary framework. | ||

+ | Alternatively, various network representations have been developed. Circular networks are a | ||

+ | natural generalization of leaf-labeled trees interpreted as split systems, that is, collections of | ||

+ | bipartitions over leaf labels corresponding to current species. Although such networks do not | ||

+ | explicitly model specific evolutionary events of interest, their straightforward visualization and | ||

+ | fast reconstruction have made them a popular exploratory tool to detect network-like evolution | ||

+ | in genetic datasets. | ||

+ | Standard reconstruction methods for circular networks rely on an | ||

+ | associated metric on the species set. Such a metric is first estimated from DNA sequences, | ||

+ | which leads to a key difficulty: distantly related sequences produce statistically unreliable | ||

+ | estimates. In the tree case, reconstruction methods have been developed using | ||

+ | the notion of a distorted metric, which captures the dependence of the error in the distance | ||

+ | through a radius of accuracy. I will present the first circular network reconstruction method | ||

+ | based on distorted metrics. This is joint work with Jason Wang. | ||

− | + | == Thursday, April 19, 2018, [https://www.math.wisc.edu/~seppalai/ Timo Seppäläinen], [https://www.math.wisc.edu UW-Madison]== | |

− | + | Title: '''Shifted weights and restricted path length in first-passage percolation''' | |

− | |||

− | |||

− | + | First-passage percolation has remained a challenging field of study since its introduction in 1965 by Hammersley and Welsh. There are many outstanding open problems. Among these are properties of the limit shape and the Euclidean length of geodesics. This talk describes a convex duality between a shift of the edge weights and the length of the geodesic, together with related results on the regularity of the limit shape as a function of the shift. The talk is based on joint work with Arjun Krishnan (Rochester) and Firas Rassoul-Agha (Utah). | |

− | == Thursday, | + | == Thursday, April 26, 2018, [http://www.math.wisc.edu/~pmwood/ Philip Matchett Wood], [http://www.math.wisc.edu/ UW-Madison] == |

− | Title: ''' | + | Title: '''Limiting eigenvalue distribution for the non-backtracking matrix of an Erdos-Renyi random graph''' |

− | Abstract: | + | Abstract: A non-backtracking random walk on a graph is a directed walk with the constraint that the last edge crossed may not be immediately crossed again in the opposite direction. This talk will give a precise description of the eigenvalues of the transition matrix for the non-backtracking random walk when the underlying graph is an Erdos-Renyi random graph on n vertices, where edges present independently with probability p. We allow p to be constant or decreasing with n, so long as p*sqrt(n) tends to infinity. The key ideas in the proof are partial derandomization, applying the Tao-Vu Replacement Principle in a novel context, and showing that partial derandomization may be interpreted as a perturbation, allowing one to apply the Bauer-Fike Theorem. Joint work with Ke Wang at HKUST (Hong Kong University of Science and Technology). |

− | + | <!-- == Thursday, May 3, 2018,TBA== | |

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | == Thursday, | ||

+ | == Thursday, May 10, 2018, TBA== | ||

+ | --> | ||

− | |||

− | |||

− | |||

− | |||

== == | == == | ||

[[Past Seminars]] | [[Past Seminars]] |

## Revision as of 10:24, 27 April 2018

# Spring 2018

**Thursdays in 901 Van Vleck Hall at 2:25 PM**, unless otherwise noted.
**We usually end for questions at 3:15 PM.**

If you would like to sign up for the email list to receive seminar announcements then please send an email to join-probsem@lists.wisc.edu.

## Thursday, February 1, 2018, Hoi Nguyen, OSU

Title: **A remark on long-range repulsion in spectrum**

Abstract: In this talk we will address a "long-range" type repulsion among the singular values of random iid matrices, as well as among the eigenvalues of random Wigner matrices. We show evidence of repulsion under arbitrary perturbation even in matrices of discrete entry distributions. In many cases our method yields nearly optimal bounds.

## Thursday, February 8, 2018, Jon Peterson, Purdue

Title: **Quantitative CLTs for random walks in random environments**

Abstract:The classical central limit theorem (CLT) states that for sums of a large number of i.i.d. random variables with finite variance, the distribution of the rescaled sum is approximately Gaussian. However, the statement of the central limit theorem doesn't give any quantitative error estimates for this approximation. Under slightly stronger moment assumptions, quantitative bounds for the CLT are given by the Berry-Esseen estimates. In this talk we will consider similar questions for CLTs for random walks in random environments (RWRE). That is, for certain models of RWRE it is known that the position of the random walk has a Gaussian limiting distribution, and we obtain quantitative error estimates on the rate of convergence to the Gaussian distribution for such RWRE. This talk is based on joint works with Sungwon Ahn and Xiaoqin Guo.

## Friday, 4pm February 9, 2018, Van Vleck B239 Wes Pegden, CMU

** This is a probability-related colloquium---Please note the unusual room, day, and time! **

Title: **The fractal nature of the Abelian Sandpile**

Abstract: The Abelian Sandpile is a simple diffusion process on the integer lattice, in which configurations of chips disperse according to a simple rule: when a vertex has at least 4 chips, it can distribute one chip to each neighbor. Introduced in the statistical physics community in the 1980s, the Abelian sandpile exhibits striking fractal behavior which long resisted rigorous mathematical analysis (or even a plausible explanation). We now have a relatively robust mathematical understanding of this fractal nature of the sandpile, which involves surprising connections between integer superharmonic functions on the lattice, discrete tilings of the plane, and Apollonian circle packings. In this talk, we will survey our work in this area, and discuss avenues of current and future research.

## Thursday, February 15, 2018, Benedek Valkó, UW-Madison

Title: **Random matrices, operators and analytic functions**

Abstract: Many of the important results of random matrix theory deal with limits of the eigenvalues of certain random matrix ensembles. In this talk I review some recent results on limits of `higher level objects' related to random matrices: the limits of random matrices viewed as operators and also limits of the corresponding characteristic functions.

Joint with B. Virág (Toronto/Budapest).

## Thursday, February 22, 2018, Garvesh Raskutti UW-Madison Stats and WID

Title: **Estimation of large-scale time series network models**

Abstract: Estimating networks from multi-variate time series data is an important problem that arises in many applications including computational neuroscience, social network analysis, and many others. Prior approaches either do not scale to multiple time series or rely on very restrictive parametric assumptions in order to guarantee mixing. In this talk, I present two approaches that provide learning guarantees for large-scale multi-variate time series. The first involves a parametric GLM framework where non-linear clipping and saturation effects that guarantee mixing. The second involves a non-parametric sparse additive model framework where beta-mixing conditions are considered. Learning guarantees are provided in both cases and theoretical results are supported both by simulation results and performance comparisons on various data examples.

## Thursday, March 8, 2018, Elnur Emrah, CMU

Title: **Busemann limits for a corner growth model with deterministic inhomogeneity**

Abstract: Busemann limits have become a useful tool in study of geodesics in percolation models. The properties of these limits are closely related to the curvature of the limit shapes in the associated growth models. In this talk, we will consider a corner growth model (CGM) with independent exponential weights. The rates of the exponentials are deterministic and inhomogeneous across columns and rows. (An equivalent model is the TASEP with step initial condition and with particlewise and holewise deterministic disorder). In particular, the model lacks stationarity. Under mild assumptions on the rates, the limit shape in our CGM exists, is concave and can develop flat regions only near the axes. In contrast, flat regions can only occur away from the axes in the CGM with general i.i.d. weights. This feature and stationarity have been instrumental in proving the existence of the Busemann limits in past work. We will discuss how to adapt and extend these arguments to establish the existence and main properties of the Busemann limits in both flat and strictly concave regions for our CGM. The results we will present are from an ongoing joint project with Chris Janjigian and Timo Seppäläinen.

## Thursday, March 15, 2018, Wenqing Hu Missouri S&T

Title: **A random perturbation approach to some stochastic approximation algorithms in optimization**

Abstract: Many large-scale learning problems in modern statistics and machine learning can be reduced to solving stochastic optimization problems, i.e., the search for (local) minimum points of the expectation of an objective random function (loss function). These optimization problems are usually solved by certain stochastic approximation algorithms, which are recursive update rules with random inputs in each iteration. In this talk, we will be considering various types of such stochastic approximation algorithms, including the stochastic gradient descent, the stochastic composite gradient descent, as well as the stochastic heavy-ball method. By introducing approximating diffusion processes to the discrete recursive schemes, we will analyze the convergence of the diffusion limits to these algorithms via delicate techniques in stochastic analysis and asymptotic methods, in particular random perturbations of dynamical systems. This talk is based on a series of joint works with Chris Junchi Li (Princeton), Weijie Su (UPenn) and Haoyi Xiong (Missouri S&T).

## Thursday, March 22, 2018, Mustazee Rahman, MIT

Title: On shocks in the TASEP

Abstract: The TASEP particle system, moving rightward, runs into traffic jams when the initial particle density to the left of the origin is smaller than the density to the right. The density function satisfies Burgers' equation and traffic jams correspond to its shocks. I will describe work with Jeremy Quastel on a specialization of the TASEP where we identify joint fluctuations of particles at the shock by using determinantal formulae for correlation functions of TASEP and its KPZ scaling limit. The limit process is expressed in terms of GOE Tracy-Widom laws.

This video shows the shock forming in Burgers' equation: https://www.youtube.com/watch?v=d49agpI0vu4

## Thursday, March 29, 2018, Spring Break

## Thursday, April 5, 2018, Qin Li, UW-Madison

Title: **PDE compression — asymptotic preserving, numerical homogenization and randomized solvers**

Abstract: All classical PDE numerical solvers are deterministic. Grids are sampled and basis functions are chosen a priori. The corresponding discrete operators are then inverted for the numerical solutions.

We study if randomized solvers could be used to compute PDEs. More specifically, for PDEs that demonstrate multiple scales, we study if the macroscopic behavior in the solution could be quickly captured via random sampling. The framework we build is general and it compresses PDE solution spaces with no analytical PDE knowledge required. The concept, when applied onto kinetic equations and elliptic equations with porous media, is equivalent to asymptotic preserving and numerical homogenization respectively.

## Thursday, April 12, 2018, Sebastien Roch, UW-Madison

Title: **Circular Networks from Distorted Metrics**

Abstract: Trees have long been used as a graphical representation of species relationships. However complex evolutionary events, such as genetic reassortments or hybrid speciations which occur commonly in viruses, bacteria and plants, do not fit into this elementary framework. Alternatively, various network representations have been developed. Circular networks are a natural generalization of leaf-labeled trees interpreted as split systems, that is, collections of bipartitions over leaf labels corresponding to current species. Although such networks do not explicitly model specific evolutionary events of interest, their straightforward visualization and fast reconstruction have made them a popular exploratory tool to detect network-like evolution in genetic datasets.

Standard reconstruction methods for circular networks rely on an associated metric on the species set. Such a metric is first estimated from DNA sequences, which leads to a key difficulty: distantly related sequences produce statistically unreliable estimates. In the tree case, reconstruction methods have been developed using the notion of a distorted metric, which captures the dependence of the error in the distance through a radius of accuracy. I will present the first circular network reconstruction method based on distorted metrics. This is joint work with Jason Wang.

## Thursday, April 19, 2018, Timo Seppäläinen, UW-Madison

Title: **Shifted weights and restricted path length in first-passage percolation**

First-passage percolation has remained a challenging field of study since its introduction in 1965 by Hammersley and Welsh. There are many outstanding open problems. Among these are properties of the limit shape and the Euclidean length of geodesics. This talk describes a convex duality between a shift of the edge weights and the length of the geodesic, together with related results on the regularity of the limit shape as a function of the shift. The talk is based on joint work with Arjun Krishnan (Rochester) and Firas Rassoul-Agha (Utah).

## Thursday, April 26, 2018, Philip Matchett Wood, UW-Madison

Title: **Limiting eigenvalue distribution for the non-backtracking matrix of an Erdos-Renyi random graph**

Abstract: A non-backtracking random walk on a graph is a directed walk with the constraint that the last edge crossed may not be immediately crossed again in the opposite direction. This talk will give a precise description of the eigenvalues of the transition matrix for the non-backtracking random walk when the underlying graph is an Erdos-Renyi random graph on n vertices, where edges present independently with probability p. We allow p to be constant or decreasing with n, so long as p*sqrt(n) tends to infinity. The key ideas in the proof are partial derandomization, applying the Tao-Vu Replacement Principle in a novel context, and showing that partial derandomization may be interpreted as a perturbation, allowing one to apply the Bauer-Fike Theorem. Joint work with Ke Wang at HKUST (Hong Kong University of Science and Technology).