## Seminars and Colloquia by Series

Series: Other Talks
Friday, November 6, 2009 - 15:00 , Location: Skiles 154 , Sergio Almada , Georgia Tech , Organizer:
We consider the Stochastic Differential Equation $dX_\epsilon=b(X_\epsilon)dt + \epsilon dW$ . Given a domain D, we study how the exit time and the distribution of the process at the time it exits D behave as \epsilon goes to 0. In particular, we cover the case in which the unperturbed system $\frac{d}{dt}x=b(x)$ has a unique fixed point of the hyperbolic type. We will illustrate how the behavior of the system is in the linear case. We will remark how our results give improvements to the study of systems admitting heteroclinic or homoclinic connections.  We will outline the general proof in two dimensions that requires normal form theory from differential equations. For higher dimensions, we introduce a new kind of non-smooth stochastic calculus.
Series: Other Talks
Wednesday, November 4, 2009 - 13:00 , Location: Skiles 255 , Farbod Shokrieh , Ga Tech , Organizer: John Etnyre
We will continue the study of derived functors between abelian categories. I will show why injective objects are needed for the construction. I will then show that, for any ringed space, the abelian category of all sheaves of Modules has enough injectives. The relation with Cech cohomology will also be studied.
Series: Other Talks
Wednesday, October 28, 2009 - 11:00 , Location: ISyE Executive Classroom , Pushkar Tripathi , ACO, Computing Science and Systems, Georgia Tech , Organizer:

Organizer: Daniel Dadush, ACO Student, ISyE

Applications in complex systems such as the Internet have spawned recent interest in studying situations involving multiple agents with their individual cost or utility functions. We introduce an algorithmic framework for studying combinatorial problems in the presence of multiple agents with submodular cost functions. We study several fundamental covering problems (Vertex Cover, Shortest Path, Perfect Matching, and Spanning Tree) in this setting and establish tight upper and lower bounds for the approximability of these problems. This talk is based on joint work with Gagan Goel, Chinmay Karande and Wang Lei. This is a joint ACO/DOS seminar, so please come a little early for pizza and refreshments sponsored by ACO.
Series: Other Talks
Saturday, October 24, 2009 - 15:10 , Location: LeCraw Auditorium , Noga Alon , Mathematics and Computer Science, Tel Aviv University , Organizer: Robin Thomas
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.
Series: Other Talks
Saturday, October 24, 2009 - 13:50 , Location: LeCraw Auditorium , Mihalis Yannakakis , Computer Science, Columbia University , Organizer: Robin Thomas
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.
Series: Other Talks
Saturday, October 24, 2009 - 12:30 , Location: LeCraw Auditorium , Richard Karp , Electrical Engineering and Computer Sciences, University of California, Berkeley , Organizer: Robin Thomas
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.
Series: Other Talks
Wednesday, October 21, 2009 - 14:00 , Location: Klaus, Room 1116 , Ravi Kannan , Microsoft Research Labs, Bangalore India , Organizer:

Tea and light refreshments 1:30 in Room 2222. Organizer: Santosh Vempala

Concentration results for the TSP, MWST and many other problems with random inputs show the answer is concentrated tightly around the mean. But most results assume uniform density of the input. We will generalize these to heavy-tailed inputs which seem to be ubiquitous in modern applications. To accomplish this, we prove two new general probability inequalities. The simpler first inequality weakens both hypotheses in Hoffding-Azuma inequality and is enough to tackle TSP, MWST and Random Projections. The second inequality further weakens the moment requirements and using it, we prove the best possible concentration for the long-studied bin packing problem as well as some others. Many other applications seem possible..
Series: Other Talks
Wednesday, October 21, 2009 - 13:00 , Location: Skiles 255 , Farbod Shokrieh , Ga Tech , Organizer: John Etnyre
As we have seen already, the global section functor is left exact.  To get a long exact sequence, I will first give the construction of derived functors in the more general setting of abelian categories withenough injectives. If time permits, I will then show that for any ringed space the category of all sheaves of Modules is an abelian category with enough injectives, and so we can construct sheaf cohomology as the right derived functors of the global section functor. The relation with Cech cohomology will be studied in a subsequent talk.
Series: Other Talks
Wednesday, October 14, 2009 - 13:00 , Location: Skiles 255 , John Etnyre , Ga Tech , Organizer: John Etnyre
We will briefly review the definition of the Cech cohomology groups of a sheaf (so if you missed last weeks talk, you should still be able to follow this weeks), discuss some basic properties of the Cech construction and give some computations that shows how the theory connects to other things (like ordinary cohomology and line bundles).
Series: Other Talks
Wednesday, October 7, 2009 - 13:00 , Location: Skiles 255 , Matt Baker , School of Mathematics, Georgia Tech , Organizer: John Etnyre
We will define the Cech cohomology groups of a sheaf and discuss some basic properties of the Cech construction.