## Seminars and Colloquia by Series

Friday, October 26, 2018 - 15:05 , Location: Skiles 156 , Jiaqi Yang , GT Math , Organizer: Jiaqi Yang
We show that, if the linearization of a map at a fixed point leaves invariant a spectral subspace, and some non-resonance conditions are satisfied. Then the map leaves invariant a smooth (as smooth as the map) manifold, which is unique among C^L invariant manifolds. Here, L only depends on the spectrum of the linearization. This is based on a work of Prof. Rafael de la Llave.
Friday, October 26, 2018 - 15:00 , Location: Skiles 005 , , Microsoft Research New England , Organizer: Lutz Warnke
We discuss some recent developments on the critical behavior of percolation on finite random networks. In a seminal paper, Aldous (1997) identified the scaling limit for the component sizes in the critical window of phase transition for the Erdos-Renyi random graph (ERRG). Subsequently, there has been a surge in the literature, revealing several interesting scaling limits of these critical components, namely, the component size, diameter, or the component itself when viewed as a metric space. Fascinatingly, when the third moment of the asymptotic degree distribution is finite, many random graph models has been shown to exhibit a universality phenomenon in the sense that their scaling exponents and limit laws are the same as the ERRG. In contrast, when the asymptotic degree distribution is heavy-tailed (having an infinite third moment), the limit law turns out to be fundamentally different from the ERRG case and in particular, becomes sensitive to the precise asymptotics of the highest degree vertices.&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; In this talk, we will focus on random graphs with a prescribed degree sequence. We start by discussing recent scaling limit results, and explore the universality classes that arise from heavy-tailed networks. Of particular interest is a new universality class that arises when the asymptotic degree distribution has an infinite second moment. Not only it gives rise to a completely new universality class, it also exhibits several surprising features that have never been observed in any other universality class so far.&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; This is based on joint works with Shankar Bhamidi, Remco van der Hofstad, Johan van Leeuwaarden and Sanchayan Sen.
Friday, October 26, 2018 - 14:00 , Location: Skiles 005 , Andreas Gross , Colorado State University , Organizer: Philipp Jell
An algorithm to compute chi-y genera of generic complete intersections&nbsp; in algebraic tori has already been known since the work of Danilov and&nbsp; Khovanskii in 1978, yet a closed formula has been given only very&nbsp; recently by Di Rocco, Haase, and Nill. In my talk, I will show how this&nbsp; formula simplifies considerably after an extension of scalars. I will&nbsp; give an algebraic explanation for this phenomenon using the Grothendieck&nbsp; rings of vector bundles on toric varieties. We will then see how the&nbsp; tropical Chern character gives rise to a refined tropicalization, which&nbsp; retains the good properties of the usual, unrefined tropicalization.
Friday, October 26, 2018 - 13:05 , Location: Skiles 005 , , CS, Duke University , , Organizer: He Guo
We study the fundamental problem of high-dimensional mean estimation in a robust model where a constant fraction of the samples are adversarially corrupted. Recent work gave the first polynomial time algorithms for this problem with dimension-independent error guarantees for several families of structured distributions.&nbsp; In this work, we give the first nearly-linear time algorithms for high-dimensional robust mean estimation. Specifically, we focus on distributions with (i) known covariance and sub-gaussian tails, and (ii) unknown bounded covariance. Given $N$ samples on $R^d$, an $\epsilon$-fraction of which may be arbitrarily corrupted, our algorithms run in time $\tilde{O}(Nd)/poly(\epsilon)$ and approximate the true mean within the information-theoretically optimal error, up to constant factors. Previous robust algorithms with comparable error guarantees have running times $\tilde{\Omega}(N d^2)$. Our algorithms rely on a natural family of SDPs parameterized by our current guess $\nu$ for the unknown mean $\mu^\star$. We give a win-win analysis establishing the following: either a near-optimal solution to the primal SDP yields a good candidate for $\mu^\star$ -- independent of our current guess $\nu$ -- or the dual SDP yields a new guess $\nu'$ whose distance from $\mu^\star$ is smaller by a constant factor. We exploit the special structure of the corresponding SDPs to show that they are approximately solvable in nearly-linear time. Our approach is quite general, and we believe it can also be applied to obtain nearly-linear time algorithms for other high-dimensional robust learning problems. This is a joint work with Ilias Diakonikolas and Rong Ge.
Thursday, October 25, 2018 - 15:05 , Location: Skiles 006 , , Texas A&M , , Organizer: Michael Damron
We prove a discrete Beurling estimate for the harmonic measure in a wedge in $\mathbf{Z}^2$, and use it to show that&nbsp;Diffusion Limited Aggregation (DLA) in a wedge of angle smaller than $\pi/4$&nbsp;stabilizes. This allows to consider the infinite DLA as a finite time growth process and questions about the number of arms, growth and dimension. I will present some conjectures and open problems. This is joint work with Ron Rosenthal (Technion) and Yuan Zhang (Pekin University).
Thursday, October 25, 2018 - 13:30 , Location: Skiles 006 , Daniel Minahan , Georgia Tech , Organizer: Trevor Gunn
We will&nbsp;discuss some basic concepts in étale cohomology and compare them to the more explicit constructions in both algebraic geometry and algebraic topology.
Thursday, October 25, 2018 - 12:00 , Location: Skiles 005 , Matthew Baker , Math, GT , Organizer: Robin Thomas
We present an algebraic framework which simultaneously generalizes the notion of linear subspaces, matroids, valuated matroids, oriented matroids, and regular matroids. &nbsp;To do this, we first introduce algebraic objects which we call pastures; they generalize both hyperfields in the sense of Krasner and partial fields in the sense of Semple and Whittle. &nbsp;We then define matroids over pastures; in fact, there are at least two natural notions of matroid in this general context, which we call weak and strong matroids. &nbsp;We present cryptomorphic'’ descriptions of each kind of matroid.&nbsp;To a (classical) rank-$r$ matroid $M$ on $E$, we can associate a universal pasture&nbsp;(resp. weak universal pasture) $k_M$ (resp. $k_M^w$). &nbsp;We show that morphisms from the universal pasture (resp. weak universal pasture) of $M$ to a pasture $F$ are canonically in bijection with strong (resp. weak) representations of $M$ over $F$. &nbsp;Similarly, the sub-pasture $k_M^f$ of $k_M^w$ generated by cross-ratios'', which we call the foundation of $M$, parametrizes rescaling classes of weak $F$-matroid structures on $M$. &nbsp;As a sample application of these considerations, we give a new proof of the fact that a matroid is regular if and only if it is both binary and orientable.
Thursday, October 25, 2018 - 11:00 , Location: Skiles 006 , , Pompeu Fabra University, Barcelona , Organizer: Mayya Zhilova
In these lectures we discuss some statistical problems with an interesting&nbsp;combinatorial structure behind. We start by reviewing the "hidden clique"&nbsp;problem, a simple prototypical example with a surprisingly rich structure.&nbsp;We also discuss various "combinatorial" testing problems and their connections&nbsp;to high-dimensional random geometric graphs. Time permitting, we study the&nbsp;problem of estimating the mean of a random variable.&nbsp;
Series: Other Talks
Thursday, October 25, 2018 - 11:00 , Location: Skiles 006 , , Pompeu Fabra University, Barcelona , , Organizer: Salvador Barone

Thanks are due to our colleague, Vladimir Koltchinskii, for arranging this visit. Please write to Vladimir if you would like to meet with Professor Gabor Lugosi during his visit, or for additional information.

In these lectures we discuss some statistical problems with an interesting combinatorial structure behind. We start by reviewing the "hidden clique" problem, a simple prototypical example with a surprisingly rich structure. We also discuss various "combinatorial" testing problems and their connections to high-dimensional random geometric graphs. Time permitting, we study the problem of estimating the mean of a random variable.
Wednesday, October 24, 2018 - 16:30 , Location: Skiles 006 , Chi-Nuo Lee , Georgia Tech , Organizer: Xingxing Yu
&nbsp;Erdős and Nešetřil conjectured in 1985 that every graph with maximum degree Δ can be strong edge colored using at most (5/4)Δ^2 colors. A&nbsp;(Δ_a,&nbsp;Δ_ b)-bipartite graphs is an&nbsp;bipartite graph such that its&nbsp;components A,B has maximum degree Δ_a,&nbsp;Δ_&nbsp;b respectively.&nbsp;R.A. Brualdi and&nbsp;J.J. Quinn Massey&nbsp;&nbsp;(1993) conjectured&nbsp;that the strong chromatic index of&nbsp;(Δ_a,&nbsp;Δ_&nbsp;b)-bipartite graphs&nbsp; is bounded by&nbsp;Δ_a*Δ_&nbsp;b.&nbsp;In this talk, we focus on a&nbsp;recent result affirming the conjecture for&nbsp;(3,&nbsp;Δ)-bipartite graphs.&nbsp;