Seminars and Colloquia by Series

Introduction to Bordered Heegaard-Floer homology

Series
Geometry Topology Working Seminar
Time
Monday, October 26, 2009 - 10:00 for 1.5 hours (actually 80 minutes)
Location
Skiles 255
Speaker
Shea Vela-VickColumbia University
We will focus on the "toy model" of bordered Floer homology. Loosely speaking, this is bordered Floer homology for grid diagrams of knots. While the toy model unfortunately does not provide us with any knot invariants, it highlights many of the key ideas needed to understand the more general theory. Note the different time and place! This is a 1.5 hour talk.

Can (Theoretical Computer) Science come to grips with Consciousness

Series
ACO Distinguished Lecture
Time
Saturday, October 24, 2009 - 17:00 for 1 hour (actually 50 minutes)
Location
LeCraw Auditorium, College of Management
Speaker
Manuel BlumComputer Science, Carnegie Mellon University

Please Note: Preceded with a reception at 4:10pm.

To come to grips with consciousness, I postulate that living entities in general, and human beings in particular, are mechanisms... marvelous mechanisms to be sure but not magical ones... just mechanisms. On this basis, I look to explain some of the paradoxes of consciousness such as Samuel Johnson's "All theory is against the freedom of the will; all experience is for it." I will explain concepts of self-awareness and free will from a mechanistic view. My explanations make use of computer science and suggest why these phenomena would exist even in a completely deterministic world. This is particularly striking for free will. The impressions of our senses, like the sense of the color blue, the sound of a tone, etc. are to be expected of a mechanism with enormously many inputs categorized into similarity classes of sight, sound, etc. Other phenomena such as the "bite" of pain are works in progress. I show the direction that my thinking takes and say something about what I've found and what I'm still looking for. Fortunately, the sciences are discovering a great deal about the brain, and their discoveries help enormously in guiding and verifying the results of this work.

Theory Day Speaker 3 - Disjoint paths, isoperimetric problems, and graph eigenvalues

Series
Other Talks
Time
Saturday, October 24, 2009 - 15:10 for 1.5 hours (actually 80 minutes)
Location
LeCraw Auditorium
Speaker
Noga AlonMathematics and Computer Science, Tel Aviv University
The spectral properties of a graph are intimately related to its structure. This can be applied in the study of discrete isoperimetric problems and in the investigation of extremal and algorithmic questions for graphs. I will discuss several recent examples illustrating this theme.

Theory Day Speaker 2 - Computational Aspects of Equilibria

Series
Other Talks
Time
Saturday, October 24, 2009 - 13:50 for 3 hours
Location
LeCraw Auditorium
Speaker
Mihalis YannakakisComputer Science, Columbia University
Many models from a variety of areas involve the computation of an equilibrium or fixed point of some kind. Examples include Nash equilibria in games; price equilibria in markets; optimal strategies and the values of competitive games (stochastic and other games); stable configurations of neural networks; analysis of the evolution of various types of dynamic stochastic models. It is not known whether these problems can be solved in polynomial time. Despite their broad diversity, there are certain common computational principles that underlie different types of equilibria and connect many of these problems to each other. In this talk we will discuss some of these common principles and the corresponding complexity classes that capture them; the effect on the complexity of the underlying computational framework; and the relationship with other open questions in computation.

Theory Day Speaker 1 - What Makes an Algorithm Great?

Series
Other Talks
Time
Saturday, October 24, 2009 - 12:30 for 2 hours
Location
LeCraw Auditorium
Speaker
Richard KarpElectrical Engineering and Computer Sciences, University of California, Berkeley
From time to time a new algorithm comes along that causes a sensation in theoretical computer science or in an area of application because of its resolution of a long-standing open question, its surprising efficiency, its practical usefulness, the novelty of its setting or approach, the elegance of its structure, the subtlety of its analysis or its range of applications. We will give examples of algorithms that qualify for greatness for one or more of these reasons, and discuss how to equip students to appreciate them and understand their strengths and weaknesses.

Random regular graphs: from spectrum to geometry and back

Series
ACO Seminar
Time
Friday, October 23, 2009 - 15:05 for 1 hour (actually 50 minutes)
Location
Skiles 255
Speaker
Eyal LubetzkyMicrosoft Research, Redmond, WA
The class of random regular graphs has been the focus of extensive study highlighting the excellent expansion properties of its typical instance. For instance, it is well known that almost every regular graph of fixed degree is essentially Ramanujan, and understanding this class of graphs sheds light on the general behavior of expanders. In this talk we will present several recent results on random regular graphs, focusing on the interplay between their spectrum and geometry. We will first discuss the relation between spectral properties and the abrupt convergence of the simple random walk to equilibrium, derived from precise asymptotics of the number of paths between vertices. Following the study of the graph geometry we proceed to its random perturbation via exponential weights on the edges (first-passage-percolation). We then show how this allows the derivation of various properties of the classical Erd\H{o}s-R\'enyi random graph near criticality. Finally, returning to the spectrum of random regular graph, we discuss the question of how close they really are to being Ramanujan and conclude with related problems involving random matrices. Based on joint works with Jian Ding, Jeong Han Kim and Yuval Peres, with Allan Sly and with Benny Sudakov and Van Vu.

Introduction to Heegaard Floer Homology

Series
Geometry Topology Working Seminar
Time
Friday, October 23, 2009 - 15:00 for 2 hours
Location
Skiles 269
Speaker
Amey KalotiGeorgia Tech

Please Note: This is a 2 hour talk.

Abstract: Heegaard floer homology is an invariant of closed 3 manifolds defined by Peter Ozsvath and Zoltan Szabo. It has proven to be a very strong invariant of 3 manifolds with connections to contact topology. In these talks we will try to define the Heegaard Floer homology without assuming much background in low dimensional topology. One more goal is to present the combinatorial description for this theory.

From transfinite diameter to order-density to best-packing: the asymptotics of ground state configurations

Series
Analysis Seminar
Time
Friday, October 23, 2009 - 14:00 for 1 hour (actually 50 minutes)
Location
Skiles 269
Speaker
Doug HardinVanderbilt University
I will review recent and classical results concerning the asymptotic properties (as N --> \infty) of 'ground state' configurations of N particles restricted to a d-dimensional compact set A\subset {\bf R}^p that minimize the Riesz s-energy functional \sum_{i\neq j}\frac{1}{|x_{i}-x_{j}|^{s}} for s>0. Specifically, we will discuss the following (1) For s < d, the ground state configurations have limit distribution as N --> \infty given by the equilibrium measure \mu_s, while the first order asymptotic growth of the energy of these configurations is given by the 'transfinite diameter' of A. (2) We study the behavior of \mu_s as s approaches the critical value d (for s\ge d, there is no equilibrium measure). In the case that A is a fractal, the notion of 'order two density' introduced by Bedford and Fisher naturally arises. This is joint work with M. Calef. (3) As s --> \infty, ground state configurations approach best-packing configurations on A. In work with S. Borodachov and E. Saff we show that such configurations are asymptotically uniformly distributed on A.

Interacting particles, series Jackson networks, and non-crossing probabilities

Series
Stochastics Seminar
Time
Thursday, October 22, 2009 - 15:00 for 1 hour (actually 50 minutes)
Location
Skiles 269
Speaker
Ton Dieker(ISyE, Georgia Tech)
In this talk, we study an interacting particle system arising in the context of series Jackson queueing networks. Using effectively nothing more than the Cauchy-Binet identity, which is a standard tool in random-matrix theory, we show that its transition probabilities can be written as a signed sum of non-crossing probabilities. Thus, questions on time-dependent queueing behavior are translated to questions on non-crossing probabilities. To illustrate the use of this connection, we prove that the relaxation time (i.e., the reciprocal of the ’spectral gap’) of a positive recurrent system equals the relaxation time of a single M/M/1 queue with the same arrival and service rates as the network’s bottleneck station. This resolves a 1985 conjecture from Blanc on series Jackson networks. Joint work with Jon Warren, University of Warwick.

Pages