Seminars and Colloquia by Series

k-planes for classification

Series
Applied and Computational Mathematics Seminar
Time
Wednesday, October 22, 2008 - 10:00 for 1 hour (actually 50 minutes)
Location
Skiles 269
Speaker
Arthur SzlamUCLA

Please Note: SPECIAL TIME AND LOCATION FOR THIS WEEK ONLY

The k-planes method is the generalization of k-means where the representatives of each cluster are affine linear sets. In this talk I will describe some possible modifications of this method for discriminative learning problems.

Quantum Physics and Algebraic Graph Theory

Series
Joint School of Mathematics and ACO Colloquium
Time
Tuesday, October 21, 2008 - 16:30 for 2 hours
Location
Skiles 255
Speaker
Chris GodsilUniversity of Waterloo

Please Note: Refreshments will be served at 4PM in Skiles 236.

The possibility of a quantum computer has lead to much new work in theoretical physics and, naturally enough, this work has raised many new mathematical problems. What is perhaps surprising is that it has lead to interesting problems in algebraic graph theory. For example, questions about the relative power of quantum computer and classical computers lead to questions about the chromatic number of certain graphs. In my talk I will discuss some of these problems, and the progress that has been made.

A PDE and a stochastic model in cell polarity

Series
PDE Seminar
Time
Tuesday, October 21, 2008 - 15:15 for 1.5 hours (actually 80 minutes)
Location
Skiles 255
Speaker
Sigurd AngenentUniversity of Wisconsin, Madison
I will discuss a few ways in which reaction diffusion models have been used to pattern formation. In particular in the setting of Cdc42 transport to and from the membrane in a yeast cell I will show a simple model which achieves polarization. The model and its analysis exhibits some striking differences between deterministic and probabilistic versions of the model.

Timing Closure in Chip Design

Series
ACO Seminar
Time
Tuesday, October 21, 2008 - 15:00 for 1 hour (actually 50 minutes)
Location
Skiles 269
Speaker
Stephan HeldUniversity of Bonn
A central characteristic of a computer chip is the speed at which it processes data, determined by the time it takes electrical signals to travel through the chip. A major challenge in the design of a chip is to achieve timing closure, that is to find a physical realization fulfilling the speed specifications. We give an overview over the major tasks for optimizing the performance of computer chips and present several new algorithms. For the topology generation of repeater trees, we introduce a variant of the Steiner tree problem and present fast algorithm that balances efficiently between the resource consumption and performance. Another indispensable task is gate sizing, a discrete optimization problem with nonlinear or PDE constraints, for which a fast heuristic is introduced. The effectiveness in practice is demonstrated by comparing with newly developed lower bounds for the achievable delay. We conclude with a variant of the time-cost tradeoff problem from project management. In contrast to the usual formulation cycles are allowed. We present a new method to compute the time-cost tradeoff curve in such instances using combinatorial algorithms. Several problems in chip design can be modeled as time-cost tradeoff problems, e.g. threshold voltage optimization of plane assignment.

Eigenvalue Inequalities for Klein-Gordon Operators

Series
Research Horizons Seminar
Time
Tuesday, October 21, 2008 - 13:00 for 1 hour (actually 50 minutes)
Location
Skiles 255
Speaker
Selma YildirimSchool of Mathematics, Georgia Tech
We consider the pseudodifferential operators H_{m,\Omega} associated by the prescriptions of quantum mechanics to the Klein-Gordon Hamiltonian when restricted to a compact domain \Omega in {\mathbb R}^d. When the mass m is 0 the operator H_{0,\Omega} coincides with the generator of the Cauchy stochastic process with a killing condition on \partial \Omega. (The operator H_{0,\Omega} is sometimes called the fractional Laplacian with power 1/2.) We prove several universal inequalities for the eigenvalues (joint work with Evans Harrell).

When Biology is Computation

Series
Other Talks
Time
Tuesday, October 21, 2008 - 11:00 for 1 hour (actually 50 minutes)
Location
Klaus Building, 1116E&W
Speaker
Leslie ValiantDivision of Engineering and Applied Sciences, Harvard University
We argue that computational models have an essential role in uncovering the principles behind a variety of biological phenomena that cannot be approached by other means. In this talk we shall focus on evolution. Living organisms function according to complex mechanisms that operate in different ways depending on conditions. Darwin's theory of evolution suggests that such mechanisms evolved through random variation guided by natural selection. However, there has existed no theory that would explain quantitatively which mechanisms can so evolve in realistic population sizes within realistic time periods, and which are too complex. Here we suggest such a theory. Evolution is treated as a form of computational learning from examples in which the course of learning depends only on the aggregate fitness of the current hypothesis on the examples, and not otherwise on individual examples. We formulate a notion of evolvability that distinguishes function classes that are evolvable with polynomially bounded resources from those that are not. For example, we can show that monotone Boolean conjunctions and disjunctions are demonstrably evolvable over the uniform distribution, while Boolean parity functions are demonstrably not. We shall discuss some broader issues in evolution and intelligence that can be addressed via such an approach.

Ribbon graphs and knots

Series
Geometry Topology Seminar
Time
Monday, October 20, 2008 - 14:00 for 1 hour (actually 50 minutes)
Location
Skiles 269
Speaker
Iain MoffattUniversity of Southern Alabama
In this talk I will describe some relations between embedded graphs, their polynomials and the Jones polynomial of an associated link. I will explain how relations between graphs, links and their polynomials leads to the definition of the partial dual of a ribbon graph. I will then go on to show that the realizations of the Jones polynomial as the Tutte polynomial of a graph, and as the topological Tutte polynomial of a ribbon graph are related, surprisingly, by the homfly polynomial.

The Erdos-Ko-Rado Theorem

Series
Combinatorics Seminar
Time
Monday, October 20, 2008 - 11:05 for 1.5 hours (actually 80 minutes)
Location
Skiles 255
Speaker
Chris Godsil University of Waterloo
In its simplest form, the Erdos-Ko-Rado theorem tells us that if we have a family F of subsets of size k from set of size v such that any two sets in the family have at least one point in common, then |F|<=(v-1)\choose(k-1) and, if equality holds, then F consists of all k-subsets that contain a given element of the underlying set. This theorem can also be viewed as a result in graph theory, and from this viewpoint it has many generalizations. I will outline how it can be proved using linear algebra, and then discuss how this approach can be applied in other cases.

Self-intersection of random paths

Series
Combinatorics Seminar
Time
Friday, October 17, 2008 - 15:00 for 1 hour (actually 50 minutes)
Location
Skiles 255
Speaker
Ravi MontenegroUniversity of Massachussetts
The Birthday Paradox says that if there are N days in a year, and 1.2*sqrt(N) days are chose uniformly at random with replacement, then there is a 50% probability that some day was chosen twice. This can be interpreted as a statement about self-intersection of random paths of length 1.2*sqrt(N) on the complete graph K_N with loops. We prove an extension which shows that for many graphs random paths with length of order sqrt(N) will have the same self-intersection property. We finish by discussing an application to the Pollard Rho Algorithm for Discrete Logarithm. (joint work with Jeong-Han Kim, Yuval Peres and Prasad Tetali).

Three closed, nonselfintersecting geodesics on the sphere

Series
Geometry Topology Working Seminar
Time
Friday, October 17, 2008 - 14:00 for 1 hour (actually 50 minutes)
Location
Skiles 269
Speaker
Jim KrysiakSchool of Mathematics, Georgia Tech
This will be a continuation of the previous talk by this title. Specifically, this will be a presentation of the classical result on the existence of three closed nonselfintersecting geodesics on surfaces diffeomorphic to the sphere. It will be accessible to anyone interested in topology and geometry.

Pages