| April 24, 2009 | ||||
| Glenn Tesler
UC San Diego |
Reconstructing the Genomic Architecture of Ancestral Mammals | |||
|
In addition to frequent single-nucleotide mutations, mammalian and
many other genomes undergo rare and dramatic changes called genome
rearrangements. These include inversions, fissions, fusions, and
translocations. Although analysis of genome rearrangements was
pioneered by Dobzhansky and Sturtevant in 1938, we still know very
little about the rearrangement events that produced the existing
varieties of genomic architectures. Recovery of mammalian
rearrangement history is a difficult combinatorial problem that I will
cover in this talk. Our data sets have included sequenced genomes
(human, mouse, rat, and others), as well as radiation hybrid maps of
additional mammals.
Co-authors: Pavel Pevzner, UCSD, Department of Computer Science and Engineering Guillaume Bourque, Genome Institute of Singapore |
||||
| April 3, 2009 | ||||
| Robert Bryant
UC Berkeley |
Auf Wiedersehen Surfaces, Revisited | |||
|
It has been known for over a century that there are many Riemannian metrics on the 2-sphere with the property that all of their geodesics are closed. Zoll, a student of Hilbert, constructed an infinite dimensional family of surfaces of rotation with this property. Following ideas of Funk, Guillemin proved that these metrics on the 2-sphere are essentially parametrized by the odd functions on the round 2-sphere. These ideas can also be applied to the understanding of Finsler metrics on the 2-sphere whose Finsler-Gauss curvature is constant, as will be explained in the talk. This leads, via the recent work of LeBrun and Mason, to a resolution of a basic problem in Finsler geometry: to describe such Finsler metrics on the 2-sphere. In this talk, no knowledge of Finsler geometry will be assumed, only a very
basic understanding of curves and surfaces. The history of the problem will be
discussed and numerous examples will be given to illustrate the underlying
ideas. |
||||
| February 20, 2009 | ||||
| Daniel Bienstock
Columbia University |
Recent Results on Lifted Formulations for Integer Programs | |||
|
Disjunctive programming is a classical technique
for 0-1optimization in which a set of vertices of the hypercube is approximated
by the convex hull of (carefully selected) polyhedra. Through the work of Lovasz,
Schriver, Sherali and Adams, and others, this can be tied with the idea of
'lifting' a formulation to a higher dimensional space, again by carefully
choosing additional variables. In this talk we will first provide an overview of this subject, and then describe a new use of this idea which leads to an approximation algorithm to the "minimum" knapsack problem:
We show that for each fixed error 0 < ε < 1, there is a
polynomial-time algorithm that produces a 0 - 1 vector satisfying constraint(*),
whose value is at most a factor of (1 + ε) larger than the optimum.
Furthermore, this approximation is obtained by rounding the solution to a linear
program. This is the first such algorithm. If time permits, we will show
generalizations of this result. Joint work with Ben McClosky.
|
||||
| November 21, 2008 | ||||
| Frank Vallentin
Centrum Wiskunde & Informatica, Amsterdam |
Fourier Analysis, Linear Programming, and Densities of Distance Avoiding Sets | |||
|
In this talk I will consider the problem of determining the
maximum density of sets in Euclidean space which avoid some given
distances, in the sense that there are no two points in the set at the
given distances. To find upper bounds for the maximum density we use
the Fourier coefficients of the autocorrelation function of the
characteristic function of a distance avoiding set together with
linear programming. This method is a continuous analog of the sphere
packing bound due to Cohn and Elkies.
I will show two applications of the bound: Computing new upper bounds
for the density of sets avoiding the unit distance in dimension
2,...,24. Giving an alternative, quantitative, and extremely simple
proof of a result of Furstenberg, Katznelson, Weiss, proved by ergodic
theoretic methods: Every planar set of positive density does not avoid
arbitrary large distances.
This is joint work with Fernando M. de Oliveira Filho.
|
||||
| November 7, 2008 | ||||
| Alejandro Adem
University of British Columbia |
Commuting Matrices and Spaces of Homomorphisms | |||
|
Let G denote a Lie group, and consider the space
of all commuting n-tuples of elements in G. In this talk we will discuss basic
topological properties of spaces such as these, and how they relate to bundle
theory, group cohomology and other interesting topological invariants. Examples
will be provided to illustrate these connections, in particular we will describe
the space of commuting pairs of elements in SU(2). The methods used will be
elementary applications of topology and representation theory.
|
||||
| October 10, 2008 | ||||
| Yuval Peres
Microsoft Research |
Hex, Random Turn Games, and the Infinity Laplacian | |||
|
The game of Hex has two players who take turns
placing stones of their respective colors on the hexagons of a rhombus-shaped
hexagonal grid. Black wins by completing a crossing between two opposite edges,
while White wins by completing a crossing between the other pair of opposite
edges. Although ordinary Hex is famously difficult to analyze, we find that
Random-Turn Hex--in which players toss a coin before each turn to decide who
gets to place the next stone--has a simple optimal strategy, related to
percolation. "Tug of war" is a two player random-turn game played as follows:
Given disjoint target sets T1
and T2 in the plane, and a token at x, toss a fair coin; the player
who wins the coin toss moves the particle up to distance r in the direction of
his/her choice. This is repeated until the token reaches a target set Ti
and player i is then declared the winner. Write ur(x) for the
probability that player 1 wins when both players play optimally. We show that as
r tends to 0, the functions ur(x) converge to the infinity harmonic
function with boundary conditions 1 on T1 and 0 on T2. Our
analysis of tug of war leads yields new estimates, and significant
generalizations, of several classical results about infinity Laplacians. I will
also describe a variant that yields p-harmonic functions for 1 < p < ∞.
(Talk based on joint works with Oded Schramm, Scott Sheffield and David Wilson.) |
||||
The University of Washington is committed to providing access, equal opportunity and reasonable accommodation in its services, programs, activities, education and employment for individuals with disabilities. To request disability accommodation, contact the Disability Services Office at least ten days in advance at: 206-543-6450/V, 206-543-6452/TTY, 206-685-3885/FAX, or dso@u.washington.edu.
