The SPAMS Schedule - Spring 2004

Abstract: Let $P$ be a set of $n$ red and $n$ blue points in general position (no three on a line) in the plane. A balanced line is a line passing through a red point and a blue point such that each open half-plane bounded by that line contains the same number of blue points as red points. In a joint work with Janos Pach, we prove a conjecture of G. Baloglou that any set $P$ as above has a least $n$ balanced lines. In the present talk we will give a different proof given later by Micha Sharir and Emo Welzl which shows the connection between this problem and the generalized lower bound theorem for polytopes. In particular this establishes the first combinatorial proof for a special case of the GLBT.

In 1944, as a student in Cambridge, Dyson wanted to find a combinatorial explanation for Ramanujan's result that the number of partitions of 5n +4 is congruent to 0 (mod 5). He defined the rank of a partition and conjectured that this would do the trick.

In 1969, Dyson finally published a proof of his conjecture. It was not the first proof published; however, the bijection he presented is remarkably simple and can be used to prove other identities such as Euler's Pentagonal Number Theorem, Gauss' Identity and generalized Euler's result that the number of partitions of n into odd parts equals the number of partitions of n into distinct parts.

Abstract: Assume you have a resource to sell to a set of users, and you want to send a message to a set of nodes in a network. You know that there is a particular cost to service any subset of users. Users will announce some prices that they would like to pay in order to get the service. How would you decide which subset of users to service? When you have decided how would you charge the cost of providing this service amongst these users. Of course, you have some goals: 1) the cost of allocation for any set of users should be fair, i.e., any subset of users should not pay more than the cost among themselves, 2) you want to prevent any group of people to lie about their real value and be better off. Thus, we would like to design a "group strategy proof mechanism." It turns out that designing such a mechanism is tightly related to designing a cost sharing for the service such that the cost share of any individual in a subset decreases as the subset gets larger. This is the definition of the cross-monotone cost sharings.

In this talk, we study the relation between these two concepts and survey a set of recent results on existence of such cost sharings on a set of combinatrial problems including set cover and metric facility location.

In a purely functional programming language such as haskell, every statement is of the form

identifier = value.

How can a set of mathematical definitions interact with the real world, e.g. send a packet across the Internet?

We will begin by defining the Hindley-Milner type system, which can automatically derive the type of an expression. As an example, the type of the "map" function is

map :: forall b a. (a -> b) -> [a] -> [b].

Then we will see how the type system cana be used to prove safety properties automatically. This will allow us to simulate imperative-style programming in a purely functional language.

Finally, the mind-body problem will be whisked away by philosopical chicanery.

Solitons are travelling waves with a permanent form. They are found in nonlinear dispersive wave systems, such as nonlinear optics or fluid surfaces. They are locally confided and remarkably stable. This causes them to act like particles and makes their interactions magically attractive.

From physical systems governed by the Maxwell's equations to the navier-Stokes equations, various partial differential equations for wave motion can be derived in the weakly nonlinear regime. These can be classified based on the kinds of dominant forces they possess. Mathematically, solitons are the steady state solutions of the time dependent nonlinear wave equation. In the last half century, many clever ideas have been introduced to solve them. Analytical approaches are mostly based on nonlinear transformations such as the similarity transform or inverse scattering transform, but these techniques are only effective for limited classes of equations. For most cases, therefore, numerical approximation by continuation is the only means to solve these equations. Moreover, efficient and accurate numerical algorithms often require the use of advanced techniques such as the spectral method.

This talk will mostly focus on fluid surface and interface systems in two and three dimensions, which produce the familiar and widely known KdV, Benjamin-Ono, KP, Benjamin, etc. solitons. Numerical simulations for the dynamics of these solitons based on the Fast Fourier Transform method will be presented. In addition, the conservation property and the integrability of the KdV equations will be briefly mentioned.

Looking at biological systems for "inspiration" for algorithms has become very popular of late in some academic circles. I will give a biased survey of some classical biological systems and the algorithms inspired by them. We will, at the very least, look at ant colonies and boids, a model inspired by schools of fish and flocks of birds. The emphasis will be more on describing interesting and entertaining algorithms and their salient properties than on rigorous description and thorough analysis.

Ramsey's Theorem givevs a nice combinatorial property of the naturals. Maybe you know it, maybe you don't; maybe I'll give a proof, and maybe I won't. The point is that it can be done. If you generalise the property, though, you soon come across properties that, if they are true of some set, force the set to be bigger than anything you have ever conceived of before (for most people anyway). So big, in fact, that the puny system commonly known as "set theory" can't prove its existence. That's something I probably will prove, modulo hand waving.

Quantum computation is an exciting and rapidly developing field that fuses ideas from computer science and quantum mechanics, and has the potential to one day revolutionize many computational problems. Starting from the basic ideas from quantum mechanics, I will introduce some of the important concepts and ideas in this field, and describe some extremely fast quantum algorithms. I will also provide a practical demonstration of quantum cryptography, which allows two individuals to communicate completely securely over large distances.

In 1985, several concepts were introduced almost simultaneously. Christos Papadimitriou defined the "games against nature" as a model for a certain kind of optimization involving randomness. Laszlo Babai came up with his "Arthur-Merlin games", enhancing the known complexity classes so as to include some problems arising in group theory. At the same time, Goldwasser, Micali, and Rackoff introduced "interactive protocols" to capture a general framework in which a powerful Prover convinces a limited Verifier about the validity of a certain statement with high probability. After a few years, all these concepts turned out to describe the same thing. I will sketch how all this is related, and how it can be useful in proving that some optimization problems are very hard.

The talk is accessible to the wide public. No prior knowledge is assumed, beyond the completion of 18.315, 18.316, 18.317, 18.318, 18.404, 18.405, 18.406, 18.407, and some additional individual study.

In some very simple situations, a possible fluid flow could simply be guessed intuitively. In others, the more elaborate procedure of solving the Navier-Stokes equations in required. However, these flows could suffer from instabilities rendering them unrealizable. I will talk about some such flows and the mechanisms behind their instabilities. In particular, I plan to briefly ddescribe the roll-wave instability, fingering instability, resuspension instability in particulate flows, Rayleigh-Benard instability and double-diffusive instabilities.

Phylogenetics is the problem of inferring the evolutionary tree relating different species based on the similarities and differences among their genomes. The problem has given rise to a variety of interesting mathematical approaches, such as distance methods and maximum likelihood. In this talk, we survey some of the combinatorial questions related to phylogenetic trees and study recent extensions of tree reconstruction based on weights of subtrees.

Long ago, in a land far away, there existed a tribe of people who cared about concrete answers. Before the formalization of calculus, these same people played with real (and sometimes imaginary) numbers. Always trying to stay in touch with the "real world," this tribe came across exotic equations that were just too hard to solve by hand. Unfortunately, the computer not having yet been discovered (or just being too lazy to use them), they were forced to come up with creative means of survival.

What they fought were wild functions and untamed differential equations ... What they did was approximate ... This is their story ... and the story of their art.