### ARC Colloquium - Saving Space by Algebraization

- Series
- Other Talks
- Time
- Wednesday, February 10, 2010 - 10:03 for 1 hour (actually 50 minutes)
- Location
- Klaus 1116W
- Speaker
- Daniel Lokshtanov – Institutt for Informatikk, Universitetet i Bergen

- You are here:
- Home
- News & Events

- Series
- Other Talks
- Time
- Wednesday, February 10, 2010 - 10:03 for 1 hour (actually 50 minutes)
- Location
- Klaus 1116W
- Speaker
- Daniel Lokshtanov – Institutt for Informatikk, Universitetet i Bergen

The Subset Sum and Knapsack problems are fundamental NP-complete problems and the pseudo-polynomial time dynamic programming algorithms for them appear in every algorithms textbook. The algorithms require pseudo-polynomial time and space. Since we do not expect polynomial time algorithms for Subset Sum and Knapsack to exist, a very natural question is whether they can be solved in pseudo-polynomial time and polynomial space. In this paper we answer this question affrmatively, and give the first pseudo-polynomial time, polynomial space algorithms for these problems. Our approach is based on algebraic methods and turns out to be useful for several other problems as well. If there is time i will also show how our method can be applied to give polynomial space exact algorithms for the classical Traveling Salesman, Weighted Set Cover and Weighted Steiner Tree problems. Joint work with Jesper Nederlof.

- Series
- Other Talks
- Time
- Friday, February 5, 2010 - 15:00 for 1 hour (actually 50 minutes)
- Location
- Klaus 1116E
- Speaker
- Jinwoo Shin – Massachusetts Institute of Technology

**Please Note:** Refreshments in Room 2222, Klaus Building from 2-3 PM.

Simple, distributed and iterative algorithms, popularly known as the message passing algorithms, have emerged as the architecture of choice for engineered networks as well as cannonical behavioral model for societal and biological networks. Despite their simplicity, message passing algorithms have been surprisingly effective. In this talk, I will try to argue in favor of such algorithms by means of two results in the context of designing efficient medium access in wireless networks and modeling agent behavior in road transportation networks. See the
full abstract,

- Series
- Other Talks
- Time
- Tuesday, February 2, 2010 - 11:00 for 1 hour (actually 50 minutes)
- Location
- Skiles 249 (Tentatively)
- Speaker
- Doug Ulmer – School of Mathematics, Georgia Tech

- Series
- Other Talks
- Time
- Thursday, January 28, 2010 - 11:00 for 1 hour (actually 50 minutes)
- Location
- Skiles 249
- Speaker
- Provost Gary Schuster – President&#039;s Office, Georgia Tech

- Series
- Other Talks
- Time
- Monday, December 7, 2009 - 08:00 for 8 hours (full day)
- Location
- University of Alabama, Birmingham
- Speaker
- Southeast Geometry Seminar – University of Alabama, Birmingham

The Southeast Geometry Seminar is a series of semiannual one-day events focusing on geometric analysis. These events are hosted in rotation by the following institutions:

- The University of Alabama at Birmingham
- The Georgia Institute of Technology
- Emory University
- The University of Tennessee Knoxville

The following five speakers will give presentations on topics that include geometric analysis, and related fields, such as partial differential equations, general relativity, and geometric topology.

- Natasa Sesum (U Penn)
- Alexandru Ionescu (U Wisconsin)
- Sergiu Klainerman (Princeton U)
- Alex Freire (U Tennessee Knoxville)
- Christian Hainzl (UAB)

A poster session will be hosted. There will also be an evening public lecture by plenary speaker Sergiu Klainerman entitled The Mathematical Magic of Black Holes.

- Series
- Other Talks
- Time
- Friday, December 4, 2009 - 15:00 for 1.5 hours (actually 80 minutes)
- Location
- Skiles 168
- Speaker
- Michelle Delcourt and Leo Chen – School of Mathematics, Georgia Tech

Leo Chen: The Shape and Stability of a Flexible Sheet in a von Karman Vortex Street

Michelle Delcourt: Dessin and Manturov bracket shuffles

In this talk we will explore the connections between knot theory and combinatorics. Links are related to Grothendieck's dessins d'enfants. Cartographic one-vertex dessins can be represented by chord diagrams. The diagrams can be recorded as "words" using a finite alphabet (k-bracket parenthesis system). Many combinatorial objects are related to these Manturov bracket structures.

- Series
- Other Talks
- Time
- Wednesday, December 2, 2009 - 13:00 for 1 hour (actually 50 minutes)
- Location
- Skiles 255
- Speaker
- Kangkang Wang – School of Mathematics, Georgia Tech

We will present a sheaf-theoretic proof of the Riemann-Roch theorem
for projective nonsingular curves.

- Series
- Other Talks
- Time
- Wednesday, November 25, 2009 - 13:00 for 1 hour (actually 50 minutes)
- Location
- Skiles 255
- Speaker
- Matt Baker – School of Mathematics, Georgia Tech

We will state Serre's fundamental finiteness and vanishing results for the cohomology
of coherent sheaves on a projective algebraic variety. As an application, we'll prove that the
constant term of the Hilbert Polynomial does not depend on the projective embedding, a fact which
is hard to understand using classical (non-cohomological) methods.

- Series
- Other Talks
- Time
- Wednesday, November 18, 2009 - 13:00 for 1 hour (actually 50 minutes)
- Location
- Skiles 255
- Speaker
- Doug Ulmer – Ga Tech

In the 60s, Grothendieck had the remarkable idea of introducing a new kind of topology where open coverings of X are no longer collections of subsets of X, but rather certain maps from other spaces to X. I will give some examples to show why this is reasonable and what one can do with it.

- Series
- Other Talks
- Time
- Wednesday, November 11, 2009 - 13:00 for 1 hour (actually 50 minutes)
- Location
- Skiles 255
- Speaker
- Farbod Shokrieh – Ga Tech

We will show that the construction of derived functors satisfy the required universal property.I will then show that, for any ringed space, the abelian category of all sheaves of Modules has enough injectives. We achieve this by first characterizing injective abelian groups (Baer's theorem).The relation with Cech cohomology will also be studied. In particular, I will show that the first Cech and Grothendieck sheaf cohomology groups are isomorphic for any topological space (without using spectral sequences).