The SPAMS Schedule - Fall 2001

I will present some accessible, fundamental open problems from Theoretical Computer Science in the language (guise?) of Pure Mathematics. Among other topics, I will discuss primality testing, algebraic lower bounds, and learning Boolean formulae.

No advanced knowledge is required to understand the talk.

Given a degenerate (n+1)-simplex in R^n, we allow all the vertices to have continuous motion inside R^n or R^{n+1}. For a given k, We give the following restriction: during the motion, the volume of some k-faces can only grow larger (these faces are called "k-struts"), while the volume of other k-faces can only become smaller ("k-cables").

We will prove that, under some specific volume restrictions on the k-faces of the (n+1)-simplex, all the volumes of the k-faces will be preserved.

The above result is also partially generalized to spherical space S^n and hyperbolic space H^n.

The focus of this talk is on understanding convex lattice polygons. After giving an exposition of the beautiful result that got me interested in this topic, I will discuss a strategy for classifying all lattice polygons. Time permitting, we'll briefly touch upon secondary matters such as the meaning of life, peace on Earth and how they'll bring Buffy back this season.

No previous knowledge of anything is assumed.

Abstract: In 1611, Johannes Kepler conjectured that the densest packing of spheres is achieved by the face-centered cubic packing (fcc). Arranged this way, the spheres fill just over 74% of the space they are packed into (in the limit of an infinite space).

In a lattice packing, all the spheres are centered at the points of a lattice. In 1831, Carl Gauss used an elegant connection between lattice packings and quadratic forms to prove that no lattice packing is denser than fcc. The general case of all packings was proved by Thomas Hales in 1998. Hales' proof relies on extensive computer calculations and is over 250 pages long.

I'll show a proof for the lattice case and, owing to limitations in both your patience and my cranial capacity, only an overview of the ideas used to prove the general case.

In practice, standard quadratic programming solvers have difficulties to compute Support Vector Machine (SVM) Training problems due to the fact that their sizes are usually very large. In this talk, we first give a general way to reduce the training problem to a sequence of smaller quadratic programming problems in order to save memory consumption and flops. We use the Conjugate Gradient method to solve each subproblem. Then to achieve more speed-up, issues like how to reduce the cost of data transferring long the computer memory hierarchy and how to make our algorithm adaptive to each problem are discussed. The resulting algorithm is very fast and memory efficient. Based on the data sets we have tried, its Matlab implementation is faster than current benchmark C++ codes. We end this talk with a discussion of how to parallel this algorithm to solve super large problems, where Matlab*P is used to implement our ideas.

We have all played with pendulums and most of us have even studied them in physics and mathematics classes. One reason being that the simple pendulum is a great means to inspire a discussion of differential equations since it is a harmonic oscillator. In this seminar I hope to convince people that the pendulum is an important phenomena to be studied in its own right.

In the unforced case, the simple pendulum has two stationary points; the one at the bottom is stable and the one at the top is unstable. This is obvious. However, by introducing periodic forcing, the governing equation generalises to Mathieu's equation and, interestingly enough, the top and bottom positions can be either stable or unstable depending on the forcing.

In this spams talk I will discuss this interesting problem and, if time permits, how it relates to my research in tidal phenomenon.

We will give an introduction to partially ordered sets, with plenty of examples and opportunities for the audience to get their hands dirty. Our main advertisement will be for that subclass known as "lattices", which have very little to do with those dots in the plane of the same name. We will present material that every self-respecting graduate student should know leading to some new results, where the emphasis will be on motivation rather than proof. Bring a pen and not your homework.

The bonus highlight of the talk will be the return appearance of Francois Blanchette, our esteemed SPAMS co-organizer.

In Wonderland, they do things a little differently. I will talk about Lewis Carroll's favorite method of computing determinants, and its connection with the fascinating story of alternating sign matrices.

It is well know that our attention span is less than twenty minutes. One consequence of this is that I have been told to keep my talk short. Another is the growth of 8-minute dating in the Boston area. We investigate this new phenomenon and show how one can use mathematics (in particular, matching theory) to create a dating agency capable of cornering the market in this lucrative area. Note that, for you convenience, even though the topic of my talk has changed the title remains the same.

Percolation is a simple mathematical model used to explain a wide variety of phenomena. However, there are still many properties of percolation systems which are not completely understood. A general description of percolation and some of its applications will be presented, followed by some recent attempts at calculate some statistical properties of percolation clusters using renormalization group theory.

Many mathematicians, pure and applied alike, have been and continue to be fascinated by the beauty and complexity of symmetric tridiagonal matrices. Personally, I've always been a BIG fan. For those of you not yet converted, I will attempt to reveal some of the aforementioned characteristics by showing you a number of (easy and beautiful, but far from trivial) facts about these matrices.

Why the title? To signify that, though their structure is very simple, their properties are far from. The alliteration is purely coincidental.

And if you wonder what this has to do with my thesis, know that I will address the question at some "almost" random point during my talk.

All are welcome. Minimal linear algebra knowledge necessary (18.06 level).

Suppose you are tiling your 2n x 2n bathroom floor with 1 x 2 rectangular tiles and would like to know how many rectangles you have to place before the tiling you have in mind can be completed in a unique way. Representing your bathroom floor as a 2n x 2n grid, this is the problem of finding the forcing number of a perfect matching M, the cardinality of the smallest subset of edges S in M such that the only perfect matching containing S is M. In this talk, we'll show how to derive bounds for forcing number of matchings for bipartite graphs and discuss some interesing results on forcing numbers for hypercubes.

The complexity of detecting various noncrossing configurations in topological graphs was known for some time. We ask the same question for geometric graphs and prove that given a geometric graph G, deciding the existence of a noncrossing perfect matching or a noncrossing spanning tree in G is NP-complete. The reductions are from 3SAT and require some crazy gadgets. Few open problems will be presented as well. This is a joint work with Geza Toth.