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

Series: Combinatorics Seminar

We study the number of random permutations needed to invariably generate the symmetric group, S_n, when the distribution of cycle counts has the strong \alpha-logarithmic property. The canonical example is the Ewens sampling formula, for which the number of k-cycles relates to a conditioned Poisson random variable with mean \alpha/k. The special case \alpha=1 corresponds to uniformly random permutations, for which it was recently shown that exactly four are needed.For strong \alpha-logarithmic measures, and almost every \alpha, we show that precisely $\lceil( 1- \alpha \log 2 )^{-1} \rceil$ permutations are needed to invariably generate S_n. A corollary is that for many other probability measures on S_n no bounded number of permutations will invariably generate S_n with positive probability. Along the way we generalize classic theorems of Erdos, Tehran, Pyber, Luczak and Bovey to permutations obtained from the Ewens sampling formula.

Series: Math Physics Seminar

Quantum theory includes many well-developed bounds for wave-functions, which can cast light on where they can be localized and where they are largely excluded by the tunneling effect. These include semiclassical estimates, especially the technique of Agmon, the use of "landscape functions," and some bounds from the theory of ordinary differential equations. With A. Maltsev of Queen Mary University I have been studying how these estimates of wave functions can be adapted to quantum graphs, which are by definition networks of one-dimensional Schrödinger equations joined at vertices.

Series: ACO Student Seminar

Stochastic
programming is concerned with decision making under uncertainty,
seeking an optimal policy with respect to a set of possible future
scenarios.
While the value of Stochastic Programming is obvious to many
practitioners, in reality uncertainty in decision making is oftentimes
neglected.
For
deterministic optimisation problems, a coherent chain of modelling and
solving exists. Employing standard modelling languages and solvers for
stochastic
programs is however difficult. First, they have (with exceptions) no
native support to formulate Stochastic Programs. Secondly solving
stochastic programs with standard solvers (e.g. MIP solvers)
is often computationally intractable.
David
will be talking about his research that aims to make Stochastic
Programming more accessible. First, he will be talking about modelling
deterministic
and stochastic programs in the Constraint Programming language MiniZinc - a modelling paradigm that retains the structure of a problem much more strongly than MIP formulations. Secondly,
he will be talking about decomposition algorithms he has been working on to solve combinatorial Stochastic Programs.

Friday, January 26, 2018 - 10:00 ,
Location: Skiles 254 ,
Trevor Gunn ,
Georgia Tech ,
tgunn@gatech.edu ,
Organizer: Kisun Lee

We will first give a quick introduction to automatic sequences. We will then outine an algebro-geometric proof of Christol's theorem discovered by David Speyer. Christol's theorem states that a formal power series f(t) over GF(p) is algebraic over GF(p)(t) if and only if there is some finite state automaton such that the n-th coefficent of f(t) is obtained by feeding in the base-p representation of n into the automaton. Time permitting, we will explain how to use the Riemann-Roch theorem to obtain bounds on the number of states in the automaton in terms of the degree, height and genus of f(t).

Series: Stochastics Seminar

Today's era of cloud computing is powered by massive data centers. A data center network enables the exchange of data in the form of packets among the servers within these data centers. Given the size of today's data centers, it is desirable to design low-complexity scheduling algorithms which result in a fixed average packet delay, independent of the size of the data center. We consider the scheduling problem in an input-queued switch, which is a good abstraction for a data center network. In particular, we study the queue length (equivalently, delay) behavior under the so-called MaxWeight scheduling algorithm, which has low computational complexity. Under various traffic patterns, we show that the algorithm achieves optimal scaling of the heavy-traffic scaled queue length with respect to the size of the switch. This settles one version of an open conjecture that has been a central question in the area of stochastic networks. We obtain this result by using a Lyapunov-type drift technique to characterize the heavy-traffic behavior of the expected total queue length in the network, in steady-state.

Series: Analysis Seminar

The investigation on Brascamp-Lieb data - their structure, their extremizability, their stability and regularity of their constants - has been an active one in Harmonic Analysis. In this talk, I'll present an example of a Brascamp-Lieb structure: a so-called Gowers structure on Euclidean spaces, together with the related Gowers-Host-Kra norms - these were originally tools in additive combinatorics context. I'll dissertate on what happens when a function nearly achieves its Gowers-Host-Kra norm in a Euclidean context - this can be seen as continuation of the work of Eisner-Tao - and a related stability result of the Gowers structure on Euclidean spaces.

Wednesday, January 24, 2018 - 13:55 ,
Location: Skiles 006 ,
Justin Lanier ,
GaTech ,
Organizer: Anubhav Mukherjee

Take a map from the interval [0,1] to itself. Such a map can be iterated, and many phenomena (such as periodic points) arise. An interval self-map is an example of a topological dynamical system that is simple enough to set up, but wildly complex to analyze. In the late 1970s, Milnor and Thurston developed a combinatorial framework for studying interval self-maps in their paper "Iterated maps of the interval". In this talk, we will give an introduction to the central questions in the study of iterated interval maps, share some illustrative examples, and lay out some of the techniques and results of Milnor and Thurston.

Series: Job Candidate Talk

Convex-geometric methods, involving random projection operators and coverings, have been successfully used in the study of the largest and smallest singular values, delocalization of eigenvectors,
and in establishing the limiting spectral distribution for certain random matrix models. Among
further applications of those methods in computer science and statistics are restricted invertibility
and dimension reduction, as well as approximation of covariance matrices of multidimensional distributions. Conversely, random linear operators play a very important role in geometric functional
analysis. In this talk, I will discuss some recent results (by my collaborators and myself) within convex geometry and the theory of random matrices, focusing on invertibility of square non-Hermitian
random matrices (with applications to numerical analysis and the study of the limiting spectral
distribution of directed d-regular graphs), approximation of covariance matrices (in particular, a
strengthening of the Bai–Yin theorem), as well as some applications of random operators in convex
geometry.

Series: Geometry Topology Seminar

Monday, January 22, 2018 - 13:55 ,
Location: Skiles 005 ,
Dr. Lee, Kiryung ,
GT ECE ,
Organizer: Sung Ha Kang

There are numerous modern applications in data science that involve inference from incomplete data. Various geometric prior models such as sparse vectors or low-rank matrices have been employed to address the ill-posed inverse problems arising in these applications. Recently, similar ideas were adopted to tackle more challenging nonlinear inverse problems such as phase retrieval and blind deconvolution. In this talk, we consider the blind deconvolution problem where the desired information as a time series is accessed as indirect observations through a time-invariant system with uncertainty. The measurements in this case is given in the form of the convolution with an unknown kernel. Particularly, we study the mathematical theory of multichannel blind deconvolution where we observe the output of multiple channels that are all excited with the same unknown input source. From these observations, we wish to estimate the source and the impulse responses of each of the channels simultaneously. We show that this problem is well-posed if the channel impulse responses follow a simple geometric model. Under these models, we show how the channel estimates can be found by solving corresponding non-convex optimization problems. We analyze methods for solving these non-convex programs, and provide performance guarantees for each.