Seminars and Colloquia by Series

Slow Mixing for the Hard-Core Model on Z^2

Series
ACO Student Seminar
Time
Friday, December 7, 2012 - 13:10 for 1 hour (actually 50 minutes)
Location
Skiles 005
Speaker
Dana Randall – College of Computing, Georgia Tech
The hard-core model has attracted much attention across several disciplines, representing lattice gases in statistical physics and independent sets in discrete mathematics and computer science. On finite graphs, we are given a parameter \lambda, and an independent set I arises with probability proportional to \lambda^{|I|}. We are interested in determining the mixing time of local Markov chains that add or remove a small number of vertices in each step. On finite regions of Z^2 it is conjectured that there is a phase transition at some critical point \lambda_c that is approximately 3.79. It is known that local chains are rapidly mixing when \lambda < 2.3882. We give complementary results showing that local chains will mix slowly when \lambda > 5.3646 on regions with periodic (toroidal) boundary conditions and when \lambda > 7.1031 with non-periodic (free) boundary conditions. The proofs use a combinatorial characterization of configurations based on the presence or absence of fault lines and an enumeration of a new class of self-avoiding walks called taxi walks. (Joint work with Antonio Blanca, David Galvin and Prasad Tetali)

A few Ways to Destroy Entropic Chaoticity

Series
Math Physics Seminar
Time
Thursday, December 6, 2012 - 16:05 for 1 hour (actually 50 minutes)
Location
Skiles 005
Speaker
Amit Einav – University of Cambridge
In this talk we will discuss the definition of chaoticity and entropic chaoticity, as well as the background that led us to define these quantities, mainly Kac's model and the Boltzmann equation. We will then proceed to investigate the fine balance required for entropic chaoticity by exploring situations where chaoticity is valid, but not entropic chaoticity. We will give a general method to construct such states as well as two explicit example, one of which is quite surprising.

Probabilities of all real zeros for random polynomials

Series
Stochastics Seminar
Time
Thursday, December 6, 2012 - 15:05 for 1 hour (actually 50 minutes)
Location
Skiles 006
Speaker
Wenbo Li – University of Delaware
There is a long history on the study of zeros of random polynomials whose coefficients are independent, identically distributed, non-degenerate random variables. We will first provide an overview on zeros of random functions and then show exact and/or asymptotic bounds on probabilities that all zeros of a random polynomial are real under various distributions. The talk is accessible to undergraduate and graduate students in any areas of mathematics.

Fluctuation of the Optimal Alignment Score via Monte Carlo

Series
Research Horizons Seminar
Time
Wednesday, December 5, 2012 - 12:05 for 1 hour (actually 50 minutes)
Location
Skiles 005
Speaker
Heinrich Matzinger – Georgia Tech, School of Math
The question of the asymptotic order of magnitude of the fluctuation of the Optimal Alignment Score of two random sequences of length n has been open for decades. We prove a relation between that order and the limit of the rescaled optimal alignment score considered as a function of the substitution matrix. This allows us to determine the asymptotic order of the fluctuation for many realistic situations up to a high confidence level.

Non equilibrium steady state for a simple model of electric conduction

Series
CDSNS Colloquium
Time
Monday, December 3, 2012 - 16:00 for 1 hour (actually 50 minutes)
Location
Skiles 006
Speaker
Federico Bonretto – Georgia Tech
A very simple model for electric conduction consists of N particles movingin a periodic array of scatterers under the influence of an electric field and of aGaussian thermostat that keeps their energy fixed. I will present analytic result for the behaviourof the steady state of the system at small electric field, where the velocity distribution becomesindependent of the geometry of the scatterers, and at large N, where the system can bedescribed by a linear Boltzmann type equation.

On the derived Witt groups of schemes

Series
Algebra Seminar
Time
Monday, December 3, 2012 - 15:05 for 1 hour (actually 50 minutes)
Location
Skiles 005
Speaker
Jeremy Jacobson – University of Georgia
The Witt group of a scheme is a globalization to schemes of the classical Witt group of a field. It is a part of a cohomology theory for schemes called the derived Witt groups. In this talk, we introduce two problems about the derived Witt groups, the Gersten conjecture and a finite generation question for arithmetic schemes, and explain recent progress on them.

Exact minimum degree thresholds for perfect matchings in uniform hypergraphs

Series
Combinatorics Seminar
Time
Friday, November 30, 2012 - 15:00 for 1 hour (actually 50 minutes)
Location
Skiles 005
Speaker
Yi Zhao – Georgia State University
Given integers k\ge 3 and d with k/2 \leq d \leq k-1, we give a minimum d-degree condition that ensures a perfect matching in a k-uniform hypergraph. This condition is best possible and extends the results of Pikhurko, R\"odl, Ruci\'{n}ski and Szemer\'edi. Our approach makes use of the absorbing method. This is a joint work with Andrew Treglown.

Near optimality in covering games by exposing global information

Series
ACO Student Seminar
Time
Friday, November 30, 2012 - 13:00 for 1 hour (actually 50 minutes)
Location
Skiles 005
Speaker
Sara Krehbiel – College of Computing, Georgia Tech
Mechanism design for distributed systems is fundamentally concerned with aligning individual incentives with social welfare to avoid socially inefficient outcomes that can arise from agents acting autonomously. One simple and natural approach is to centrally broadcast non-binding advice intended to guide the system to a socially near-optimal state while still harnessing the incentives of individual agents. The analytical challenge is proving fast convergence to near optimal states, and we present the first results that carefully constructed advice vectors yield stronger guarantees. We apply this approach to a broad family of potential games modeling vertex cover and set cover optimization problems in a distributed setting. This class of problems is interesting because finding exact solutions to their optimization problems is NP-hard yet highly inefficient equilibria exist, so a solution in which agents simply locally optimize is not satisfactory. We show that with an arbitrary advice vector, a set cover game quickly converges to an equilibrium with cost of the same order as the square of the social cost of the advice vector. More interestingly, we show how to efficiently construct an advice vector with a particular structure with cost $O(\log n)$ times the optimal social cost, and we prove that the system quickly converges to an equilibrium with social cost of this same order.

Smoothness properties for some infinite-dimensional heat kernel measures

Series
Stochastics Seminar
Time
Thursday, November 29, 2012 - 15:05 for 1 hour (actually 50 minutes)
Location
Skiles 006
Speaker
Tai Melcher – University of Virginia
Smoothness is a fundamental principle in the study of measures on infinite-dimensional spaces, where an obvious obstruction to overcome is the lack of an infinite-dimensional Lebesgue or volume measure. Canonical examples of smooth measures include those induced by a Brownian motion, both its end point distribution and as a real-valued path. More generally, any Gaussian measure on a Banach space is smooth. Heat kernel measure is the law of a Brownian motion on a curved space, and as such is the natural analogue of Gaussian measure there. We will discuss some recent smoothness results for these measures on certain classes of infinite-dimensional groups, including in some degenerate settings. This is joint work with Fabrice Baudoin, Daniel Dobbs, and Masha Gordina.

Pages